login
a(n) = 5*a(n-1) - a(n-2) for n > 1, a(0) = 0, a(1) = 1.
(Formerly M3930)
73

%I M3930 #131 Aug 17 2024 14:23:13

%S 0,1,5,24,115,551,2640,12649,60605,290376,1391275,6665999,31938720,

%T 153027601,733199285,3512968824,16831644835,80645255351,386394631920,

%U 1851327904249,8870244889325,42499896542376,203629237822555,975646292570399,4674602225029440

%N a(n) = 5*a(n-1) - a(n-2) for n > 1, a(0) = 0, a(1) = 1.

%C Nonnegative values of y satisfying x^2 - 21*y^2 = 4; values of x are in A003501. - _Wolfdieter Lang_, Nov 29 2002

%C a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 5's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - _John M. Campbell_, Jun 09 2011

%C For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,2,3,4}. - _Milan Janjic_, Jan 25 2015

%C Lim_{n->oo} a(n+1)/a(n) = (5 + sqrt(21))/2 = A107905. - _Wolfdieter Lang_, Nov 15 2023

%C From _Klaus Purath_, Jul 26 2024: (Start)

%C For any three consecutive terms (x, y, z), y^2 - xz = 1 always applies.

%C a(n) = (t(i+2n) - t(i))/(t(i+n+1) - t(i+n-1)) where (t) is any recurrence t(k) = 4t(k-1) + 4t(k-2) - t(k-3) or t(k) = 5t(k-1) - t(k-2) without regard to initial valus.

%C In particular, if the recurrence (t) of the form (4,4,-1) has the same three initial values as the current sequence, a(n) = t(n) applies.

%C a(n) = (t(k+1)*t(k+n) - t(k)*t(k+n+1))/(y^2 - xz) where (t) is any recurrence of the current family with signature (5,-1) and (x, y, z) are any three consecutive terms of (t), for integer k >= 0. (End)

%D F. A. Haight, On a generalization of Pythagoras' theorem, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Indranil Ghosh, <a href="/A004254/b004254.txt">Table of n, a(n) for n = 0..1467</a> (terms 0..200 from T. D. Noe)

%H Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, <a href="https://www.emis.de/journals/INTEGERS/papers/p38/p38.Abstract.html">Polynomial sequences on quadratic curves</a>, Integers, Vol. 15, 2015, #A38.

%H K. Andersen, L. Carbone, and D. Penta, <a href="https://pdfs.semanticscholar.org/8f0c/c3e68d388185129a56ed73b5d21224659300.pdf">Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields</a>, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.

%H Francesca Arici and Jens Kaad, <a href="https://arxiv.org/abs/2012.11186">Gysin sequences and SU(2)-symmetries of C*-algebras</a>, arXiv:2012.11186 [math.OA], 2020.

%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3 , Example 12

%H Chair, Noureddine <a href="https://doi.org/10.1016/j.aop.2012.09.002">Exact two-point resistance, and the simple random walk on the complete graph minus N edges</a>, Ann. Phys. 327, No. 12, 3116-3129 (2012), B(7).

%H E. I. Emerson, <a href="http://www.fq.math.ca/Scanned/7-3/emerson.pdf">Recurrent Sequences in the Equation DQ^2=R^2+N</a>, Fib. Quart., 7 (1969), pp. 231-242.

%H Dale Gerdemann, <a href="https://www.youtube.com/watch?v=hZFnWYPL1Uk">Fractal images from (5,-1) recursion</a>, YouTube Video, Nov 05 2014.

%H Dale Gerdemann, <a href="https://www.youtube.com/watch?v=Fz5NY7b5dSQ">Fractal images from (5,-1) recursion: Selections in detail</a>, YouTube Video, Nov 05 2014.

%H Frank A. Haight, <a href="/A004253/a004253_1.pdf">Letter to N. J. A. Sloane, Sep 06 1976</a>

%H Frank A. Haight, <a href="/A004253/a004253.pdf">On a generalization of Pythagoras' theorem</a>, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971. [Annotated scanned copy]

%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/5-5/horadam.pdf">Special properties of the sequence W_n(a,b; p,q)</a>, Fib. Quart., 5.5 (1967), 424-434. Case a=0,b=1; p=5, q=-1.

%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/9-3/horadam-a.pdf">Pell Identities</a>, Fib. Quart., Vol. 9, No. 3, 1971, pp. 245-252.

%H M. Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Wolfdieter Lang, <a href="http://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38,5 (2000) 408-419; Eq.(44), lhs, m=7.

%H Ioana-Claudia Lazăr, <a href="https://arxiv.org/abs/1904.06555">Lucas sequences in t-uniform simplicial complexes</a>, arXiv:1904.06555 [math.GR], 2019.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H F. M. van Lamoen, <a href="http://forumgeom.fau.edu/FG2006volume6/FG200637index.html">Square wreaths around hexagons</a>, Forum Geometricorum, 6 (2006) 311-325.

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

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

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

%F a(n) = ((5+sqrt(21))/2)^n-((5-sqrt(21))/2)^n)/sqrt(21). - _Barry E. Williams_, Aug 29 2000

%F a(n) = S(2*n-1, sqrt(7))/sqrt(7) = S(n-1, 5); S(n, x)=U(n, x/2), Chebyshev polynomials of 2nd kind, A049310.

%F A003501(n) = sqrt(21*a(n)^2 + 4).

%F a(n) = Sum_{k=0..n-1} binomial(n+k, 2*k+1)*2^k. - _Paul Barry_, Nov 30 2004

%F [A004253(n), a(n)] = [1,3; 1,4]^n * [1,0]. - _Gary W. Adamson_, Mar 19 2008

%F a(n+1) = Sum_{k=0..n} Gegenbauer_C(n-k,k+1,2). - _Paul Barry_, Apr 21 2009

%F a(n+1) = Sum_{k=0..n} A101950(n,k)*4^k. - _Philippe Deléham_, Feb 10 2012

%F Product {n >= 1} (1 + 1/a(n)) = (1/3)*(3 + sqrt(21)). - _Peter Bala_, Dec 23 2012

%F Product {n >= 2} (1 - 1/a(n)) = (1/10)*(3 + sqrt(21)). - _Peter Bala_, Dec 23 2012

%F A054493(2*n - 1) = 7 * a(n)^2 for all n in Z. - _Michael Somos_, Jan 22 2017

%F a(n) = -a(-n) for all n in Z. - _Michael Somos_, Jan 22 2017

%F 0 = -1 + a(n)*(+a(n) - 5*a(n+1)) + a(n+1)*(+a(n+1)) for all n in Z. - _Michael Somos_, Jan 22 2017

%F From _Klaus Purath_, Jul 26 2024: (Start)

%F a(n) = 4(a(n-1) + a(n-2)) - a(n-3).

%F a(n) = 6(a(n-1) - a(n-2)) + a(n-3).

%F In general, for all sequences of the form U(n) = P*U(n-1) - U(n-2) the following applies:

%F U(n) = (P-1)*U(n-1) + (P-1)*U(n-2) - U(n-3).

%F U(n) = (P+1)*U(n-1) - (P+1)*U(n-2) + U(n-3). (End)

%e G.f. = x + 5*x^2 + 24*x^3 + 115*x^4 + 551*x^5 + 2640*x^6 + 12649*x^7 + ...

%p A004254:=1/(1-5*z+z**2); # _Simon Plouffe_ in his 1992 dissertation

%t a[n_]:=(MatrixPower[{{1,3},{1,4}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 19 2010 *)

%t a[ n_] := ChebyshevU[2 n - 1, Sqrt[7]/2] / Sqrt[7]; (* _Michael Somos_, Jan 22 2017 *)

%o (PARI) {a(n) = subst(4*poltchebi(n+1) - 10*poltchebi(n), x, 5/2) / 21}; /* _Michael Somos_, Dec 04 2002 */

%o (PARI) {a(n) = imag((5 + quadgen(84))^n) / 2^(n-1)}; /* _Michael Somos_, Dec 04 2002 */

%o (PARI) {a(n) = polchebyshev(n - 1, 2, 5/2)}; /* _Michael Somos_, Jan 22 2017 */

%o (PARI) {a(n) = simplify( polchebyshev( 2*n - 1, 2, quadgen(28)/2) / quadgen(28))}; /* _Michael Somos_, Jan 22 2017 */

%o (Sage) [lucas_number1(n,5,1) for n in range(27)] # _Zerinvary Lajos_, Jun 25 2008

%o (Magma) [ n eq 1 select 0 else n eq 2 select 1 else 5*Self(n-1)-Self(n-2): n in [1..30] ]; // _Vincenzo Librandi_, Aug 19 2011

%Y Partial sums of A004253.

%Y Cf. A000027, A001906, A001353, A003501, A030221. a(n) = sqrt((A003501(n)^2 - 4)/21).

%Y First differences of a(n) are in A004253, partial sums in A089817.

%Y Cf. A004253.

%Y INVERT transformation yields A001109. - _R. J. Mathar_, Sep 11 2008

%Y Cf. A054493, A107905.

%K easy,nonn,easy

%O 0,3

%A _N. J. A. Sloane_