A095932 Number of walks of length 2n+1 between two nodes at distance 3 in the cycle graph C_10.

1, 5, 22, 93, 385, 1574, 6385, 25773, 103702, 416405, 1669801, 6690150, 26789257, 107232053, 429124630, 1717012749, 6869397265, 27481113638, 109933682017, 439758885885, 1759098789526, 7036560738245, 28146676447417, 112587840692838, 450354333986425

Offset

1,2

Comments

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=3.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (7,-13,4).

Formula

a(n) = 4^n/5*Sum_{r=0..9} cos(3*Pi*r/5)*cos(Pi*r/5)^(2*n+1).

a(n) = 7*a(n-1)-13*a(n-2)+4*a(n-3).

G.f.: (-x+2*x^2)/((-1+4*x)*(1-3*x+x^2)).

a(n) = (2^(1+2*n)-(1/2*(3-sqrt(5)))^n-(1/2*(3+sqrt(5)))^n)/5. - Colin Barker, Apr 27 2016

E.g.f.: (2*exp(4*x) - exp(((3 - sqrt(5))*x)/2) - exp(((3 + sqrt(5))*x)/2))/5. - Ilya Gutkovskiy, Apr 27 2016

From Greg Dresden, Jan 19 2023: (Start)

a(n) = Sum_{k>0} binomial(2*n,n+k)-binomial(2*n,n+5k).

5*a(n) = 2*4^n - Lucas(2*n). (End)

Mathematica

f[n_]:=FullSimplify[TrigToExp[(4^n/5)Sum[Cos[3Pi*k/5]Cos[Pi*k/5]^(2n+1), {k, 0, 9}]]]; Table[f[n], {n, 1, 35}]

Prog

(PARI) Vec((-x+2*x^2)/((-1+4*x)*(1-3*x+x^2)) + O(x^50)) \\ Colin Barker, Apr 27 2016

Crossrefs

A000032.

Sequence in context: A278472 A010036 A127617 * A000346 A289798 A026672

Adjacent sequences: A095929 A095930 A095931 * A095933 A095934 A095935

Keyword

nonn,easy

Author

Herbert Kociemba, Jul 12 2004

Status

approved