A052918 a(0) = 1, a(1) = 5, a(n+1) = 5*a(n) + a(n-1).

1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, 51872282415, 269351100901, 1398627786920, 7262490035501, 37711077964425, 195817879857626

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

A087130(n)^2 - 29*a(n-1)^2 = 4*(-1)^n, n >= 1. - Gary W. Adamson, Jul 01 2003, corrected Oct 07 2008, corrected by Jianing Song, Feb 01 2019

a(p-1) == 29^((p-1)/2) (mod p), for odd primes p. - Gary W. Adamson, Feb 22 2009 [See A087475 for more info about this congruence. - Jason Yuen, Apr 05 2025]

For more information about this type of recurrence, follow the Khovanova link and see A054413, A086902 and A178765. - Johannes W. Meijer, Jun 12 2010

Binomial transform of A015523. - Johannes W. Meijer, Aug 01 2010

For positive n, a(n) equals the permanent of the n X n tridiagonal matrix with 5's along the main diagonal and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011

a(n) equals the number of words of length n on alphabet {0,1,...,5} avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015

From Michael A. Allen, Feb 15 2023: (Start)

Also called the 5-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.

a(n) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 5 kinds of squares available. (End)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.
• D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 8.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 901
• Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
• Milan Janjić, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Tanya Khovanova, Recursive Sequences
• Kai Wang, On k-Fibonacci Sequences And Infinite Series List of Results and Examples, 2020.
• Index entries for sequences related to Chebyshev polynomials.
• Index entries for linear recurrences with constant coefficients, signature (5,1).

Crossrefs

Row 5 of A073133, A172236, and A352361.

Cf. A087130, A099365 (squares), A100237, A175184 (Pisano periods), A201005 (prime subsequence).

Programs

GAP

a:=[1,5];; for n in [3..30] do a[n]:=5*a[n-1]+a[n-2]; od; a; # G. C. Greubel, Oct 16 2019

Magma

I:=[1, 5]; [n le 2 select I[n] else 5*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, Feb 23 2013

Magma

R:=PowerSeriesRing(Integers(), 22); Coefficients(R!( 1/(1 - 5*x - x^2) )); // Marius A. Burtea, Oct 16 2019

Maple

spec := [S,{S=Sequence(Union(Z,Z,Z,Z,Z,Prod(Z,Z)))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..30);
a[0]:=1: a[1]:=5: for n from 2 to 26 do a[n]:=5*a[n-1]+a[n-2] od: seq(a[n], n=0..30); # Zerinvary Lajos, Jul 26 2006
with(combinat):a:=n->fibonacci(n,5):seq(a(n),n=1..30); # Zerinvary Lajos, Dec 07 2008

Mathematica

LinearRecurrence[{5, 1}, {1, 5}, 30] (* Vincenzo Librandi, Feb 23 2013 *)
Table[Fibonacci[n+1, 5], {n,0,30}] (* Vladimir Reshetnikov, May 08 2016 *)

PARI

Vec(1/(1-5*x-x^2)+O(x^30)) \\ Charles R Greathouse IV, Nov 20 2011

Sage

[lucas_number1(n,5,-1) for n in range(1, 22)] # Zerinvary Lajos, Apr 24 2009

Formula

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

a(3n) = A041047(5n), a(3n+1) = A041047(5n+3), a(3n+2) = 2*A041047(5n+4). - Henry Bottomley, May 10 2000

a(n) = Sum_{alpha=RootOf(-1+5*z+z^2)} (1/29)*(5+2*alpha)*alpha^(-1-n).

a(n-1) = (((5 + sqrt(29))/2)^n - ((5 - sqrt(29))/2)^n)/sqrt(29). - Gary W. Adamson, Jul 01 2003

a(n) = U(n, 5*i/2)*(-i)^n with i^2 = -1 and Chebyshev's U(n, x/2) = S(n, x) polynomials. See triangle A049310.

Let M = {{0, 1}, {1, 5}}, then a(n) is the lower-right term of M^n. - Roger L. Bagula, May 29 2005

a(n) = F(n, 5), the n-th Fibonacci polynomial evaluated at x = 5. - T. D. Noe, Jan 19 2006

a(n) = denominator of n-th convergent to [1, 4, 5, 5, 5, ...], for n > 0. Continued fraction [1, 4, 5, 5, 5, ...] = 0.807417596..., the inradius of a right triangle with legs 2 and 5. n-th convergent = A100237(n)/A052918(n), the first few being: 1/1, 4/5, 21/26, 109/135, 566/701, ... - Gary W. Adamson, Dec 21 2007

From Johannes W. Meijer, Jun 12 2010: (Start)

a(2n+1) = 5*A097781(n), a(2n) = A097835(n).

Limit_{k->oo} a(n+k)/a(k) = (A087130(n) + a(n-1)*sqrt(29))/2.

Limit_{n->oo} A087130(n)/a(n-1) = sqrt(29). (End)

From L. Edson Jeffery, Jan 07 2012: (Start)

Define the 2 X 2 matrix A = {{1, 1}, {5, 4}}. Then:

a(n) is the upper-left term of (1/5)*(A^(n+2) - A^(n+1));

a(n) is the upper-right term of A^(n+1);

a(n) is the lower-left term of (1/5)*A^(n+1);

a(n) is the lower-right term of (Sum_{k=0..n} A^k). (End)

Sum_{n>=0} (-1)^n/(a(n)*a(n+1)) = (sqrt(29) - 5)/2. - Vladimir Shevelev, Feb 23 2013

G.f.: x/(1 - 5*x - x^2) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (m*k + 5 - m + x)/(1 + m*k*x) ) for arbitrary m (a telescoping series). - Peter Bala, May 08 2024