|
%I #29 Sep 08 2022 08:45:13
%S 1,7,36,165,715,3004,12393,50559,204820,826045,3321891,13333932,
%T 53457121,214146295,857417220,3431847189,13733091643,54947296924,
%U 219828275865,879415437615,3517929664756,14072420067757,56291516582931,225170873858700,900696081703825
%N Number of walks of length 2n between two nodes at distance 4 in the cycle graph C_10.
%C In general 2^n/m*Sum_{r=0..m-1} Cos(2Pi*k*r/m)Cos(2Pi*r/m)^n is the number of walks of length n between two nodes at distance k in the cycle graph C_m. Here we have m=10 and k=4.
%H G. C. Greubel, <a href="/A095931/b095931.txt">Table of n, a(n) for n = 2..1000</a>
%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Note on Cosine Power Sums</a> J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-13,4).
%F a(n) = 7*a(n-1) - 13*a(n-2) + 4*a(n-3).
%F G.f.: x^2/((1-4*x)*(1-3*x+x^2)).
%F a(n) = 4^n/(10*Sum_{r=0..9} cos(4*Pi*r/5)*cos(Pi*r/5)^(2*n) ).
%F From _Mircea Merca_, Jun 25 2011: (Start)
%F a(n) = (4^n - (2*cos(Pi/5))^(2*n+1) + (2*cos(2*Pi/5))^(2*n+1))/5.
%F a(n) = (4^n - ((sqrt(5)+1)/2)^(2*n+1) + ((sqrt(5)-1)/2)^(2*n+1))/5.
%F a(n) = Sum_{k=1..floor((n+3)/5)} C(2*n+1,n+3-5*k). (End)
%F 5*a(n) = 4^n - A002878(n). - _R. J. Mathar_, Oct 13 2012
%p seq(sum(binomial(2*n+1, n+3-5*k),k=1..floor((n+3)*(1/5))),n=2..20) # _Mircea Merca_, Jun 25 2011
%t f[n_]:=FullSimplify[TrigToExp[(4^n/10)Sum[Cos[4Pi*k/5]Cos[Pi*k/5]^(2n), {k, 0, 9}]]];Table[f[n], {n, 2, 35}]
%t LinearRecurrence[{7, -13, 4}, {1, 7, 36}, 25] (* _Vincenzo Librandi_, Dec 20 2018 *)
%o (PARI) x='x+O('x^66); /* that many terms */
%o Vec(x^2/((1-4*x)*(1-3*x+x^2))) /* show terms */ /* _Joerg Arndt_, Jun 25 2011 */
%o (GAP) a:=[1,7,36];; for n in [4..25] do a[n]:=7*a[n-1]-13*a[n-2]+4*a[n-3]; od; a; # _Muniru A Asiru_, Dec 19 2018
%o (Magma) I:=[1,7,36]; [n le 3 select I[n] else 7*Self(n-1)-13*Self(n-2)+4*Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Dec 20 2018
%K nonn
%O 2,2
%A _Herbert Kociemba_, Jul 12 2004
| 