OFFSET
0,2
COMMENTS
Number of walks of length 2*n+1 between two adjacent vertices in the cycle graph C_10. - Herbert Kociemba, Jul 02 2004
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Index entries for linear recurrences with constant coefficients, signature (7,-13,4).
FORMULA
G.f.: (1 - 4*x + 2*x^2) / (1 - 7*x + 13*x^2 - 4*x^3).
From Herbert Kociemba, Jul 02 2004: (Start)
a(n) = [4^(n+1) + (sqrt(5)+3)*phi^(2n) - (sqrt(5)-3)*phi^(-2n)]/10, where phi is the golden ratio (1+sqrt(5))/2.
a(n) = 7a(n-1)-13a(n-2)+4a(n-3). (End)
a(n) = Sum_{k= -floor(n/5)..floor(n/5)} binomial(2*n,n+5*k)/2 = ((3+sqrt(5))^n + (3-sqrt(5))^n + 2^(3*n-1))/(5*2^n). - Mircea Merca, Jan 28 2012
a(n) = (Lucas(2*n+2) + 2^(2*n+1))/5. - Greg Dresden, Jan 26 2023
MATHEMATICA
LinearRecurrence[{7, -13, 4}, {1, 3, 10}, 25] (* Vincenzo Librandi, Dec 18 2018 *)
CoefficientList[Series[(1-4x+2x^2)/(1-7x+13x^2-4x^3), {x, 0, 40}], x] (* Harvey P. Dale, Feb 17 2024 *)
PROG
(PARI) {a(n) = polcoeff( (1 - 4*x + 2*x^2) / (1 - 7*x + 13*x^2 - 4*x^3) + x * O(x^n), n)}
(PARI) {a(n) = sum( k=-n\5, n\5, binomial(2*n + 1, n+1 + 5*k))}
(Magma) I:=[1, 3, 10]; [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 18 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Michael Somos, Dec 03 2002
STATUS
approved