A015531 Linear 2nd order recurrence: a(n) = 4*a(n-1) + 5*a(n-2).

0, 1, 4, 21, 104, 521, 2604, 13021, 65104, 325521, 1627604, 8138021, 40690104, 203450521, 1017252604, 5086263021, 25431315104, 127156575521, 635782877604, 3178914388021, 15894571940104, 79472859700521, 397364298502604, 1986821492513021, 9934107462565104

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

Number of walks of length n between any two distinct vertices of the complete graph K_6. Example: a(2)=4 because the walks of length 2 between the vertices A and B of the complete graph ABCDEF are: ACB, ADB, AEB and AFB. - Emeric Deutsch, Apr 01 2004

General form: k=5^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-4, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - Milan Janjic, Jan 27 2010

Pisano period lengths: 1, 2, 6, 2, 2, 6, 6, 4, 18, 2, 10, 6, 4, 6, 6, 8, 16, 18, 18, 2,... - R. J. Mathar, Aug 10 2012

The ratio a(n+1)/a(n) converges to 5 as n approaches infinity. - Felix P. Muga II, Mar 09 2014

For odd n, a(n) is congruent to 1 (mod 10). For even n > 0, a(n) is congruent to 4 (mod 10). - Iain Fox, Dec 30 2017

Links

• Iain Fox, Table of n, a(n) for n = 0..1431 (terms 0..1000 from Vincenzo Librandi)
• Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
• F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014.
• Index entries for linear recurrences with constant coefficients, signature (4,5).

Crossrefs

A083425 shifted right.

Cf. A033115 (partial sums), A213128.

Programs

Magma

[Round(5^n/6): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

Maple

seq(round(5^n/6), n=0..25); # Mircea Merca, Dec 28 2010

Mathematica

LinearRecurrence[{4,5},{0,1},30] (* Harvey P. Dale, Jul 09 2017 *)

PARI

a(n)=5^n\/6 ; \\ Charles R Greathouse IV, Apr 14 2014

PARI

first(n) = Vec(x/((1 - 5*x)*(1 + x)) + O(x^n), -n) \\ Iain Fox, Dec 30 2017

Sage

[lucas_number1(n,4,-5) for n in range(0, 22)] # Zerinvary Lajos, Apr 23 2009

Formula

From Paul Barry, Apr 20 2003: (Start)

a(n) = (5^n -(-1)^n)/6.

G.f.: x/((1-5*x)*(1+x)).

E.g.f.(exp(5*x)-exp(-x))/6. (End) (corrected by M. F. Hasler, Jan 29 2012)

a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*6^(k-1). - Paul Barry, May 13 2003

a(n) = 5^(n-1) - a(n-1). - Emeric Deutsch, Apr 01 2004

a(n) = ((2+sqrt(9))^n - (2-sqrt(9))^n)/6. - Al Hakanson (hawkuu(AT)gmail.com), Jan 07 2009

a(n) = round(5^n/6). - Mircea Merca, Dec 28 2010

The logarithmic generating function 1/6*log((1+x)/(1-5*x)) = x + 4*x^2/2 + 21*x^3/3 + 104*x^4/4 + ... has compositional inverse 6/(5+exp(-6*x)) - 1, the e.g.f. for a signed version of A213128. - Peter Bala, Jun 24 2012

a(n) = (-1)^(n-1)*Sum_{k=0..(n-1)} A135278(n-1,k)*(-6)^k = (5^n - (-1)^n)/6 = (-1)^(n-1)*Sum_{k=0..(n-1)} (-5)^k. Equals (-1)^(n-1)*Phi(n,-5) when n is an odd prime, where Phi is the cyclotomic polynomial. - Tom Copeland, Apr 14 2014