%I #83 Aug 04 2024 19:10:04

%S 0,1,4,21,104,521,2604,13021,65104,325521,1627604,8138021,40690104,

%T 203450521,1017252604,5086263021,25431315104,127156575521,

%U 635782877604,3178914388021,15894571940104,79472859700521

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

%C 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

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

%C 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

%C 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

%C The ratio a(n+1)/a(n) converges to 5 as n approaches infinity. - _Felix P. Muga II_, Mar 09 2014

%C 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

%H Iain Fox, <a href="/A015531/b015531.txt">Table of n, a(n) for n = 0..1431</a> (terms 0..1000 from Vincenzo Librandi)

%H Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, Jiemeng Zhang, <a href="https://arxiv.org/abs/1911.01687">Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences</a>, arXiv:1911.01687 [math.CO], 2019.

%H F. P. Muga II, <a href="https://www.researchgate.net/publication/267327689_Extending_the_Golden_Ratio_and_the_Binet-de_Moivre_Formula">Extending the Golden Ratio and the Binet-de Moivre Formula</a>, March 2014.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,5).

%F From _Paul Barry_, Apr 20 2003: (Start)

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

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

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

%F a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*6^(k-1). - _Paul Barry_, May 13 2003

%F a(n) = 5^(n-1) - a(n-1). - _Emeric Deutsch_, Apr 01 2004

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

%F a(n) = round(5^n/6). - _Mircea Merca_, Dec 28 2010

%F 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

%F 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

%p seq(round(5^n/6), n=0..25); # _Mircea Merca_, Dec 28 2010

%t LinearRecurrence[{4,5},{0,1},30] (* _Harvey P. Dale_, Jul 09 2017 *)

%o (Sage) [lucas_number1(n,4,-5) for n in range(0, 22)] # _Zerinvary Lajos_, Apr 23 2009

%o (Magma) [Round(5^n/6): n in [0..30]]; // _Vincenzo Librandi_, Jun 24 2011

%o (PARI) a(n)=5^n\/6 ; \\ _Charles R Greathouse IV_, Apr 14 2014

%o (PARI) first(n) = Vec(x/((1 - 5*x)*(1 + x)) + O(x^n), -n) \\ _Iain Fox_, Dec 30 2017

%Y A083425 shifted right.

%Y Cf. A033115 (partial sums), A213128.

%K nonn,easy

%O 0,3

%A _Olivier Gérard_