A006131 a(n) = a(n-1) + 4*a(n-2), a(0) = a(1) = 1.

1, 1, 5, 9, 29, 65, 181, 441, 1165, 2929, 7589, 19305, 49661, 126881, 325525, 833049, 2135149, 5467345, 14007941, 35877321, 91909085, 235418369, 603054709, 1544728185, 3956947021, 10135859761, 25963647845, 66507086889, 170361678269

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Length-n words with letters {0,1,2,3,4} where no two consecutive letters are nonzero, see fxtbook link below. - Joerg Arndt, Apr 08 2011

Equals INVERTi transform of A063727: (1, 2, 8, 24, 80, 256, 832, ...). - Gary W. Adamson, Aug 12 2010

a(n) is equal to the permanent of the n X n Hessenberg matrix with 1's along the main diagonal, 2's along the superdiagonal and the subdiagonal, and 0's everywhere else. - John M. Campbell, Jun 09 2011

The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 2, 5*a(n-2) equals the number of 5-colored compositions of n with all parts >= 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011

Pisano period lengths: 1, 1, 8, 1, 6, 8, 48, 2, 24, 6,120, 8, 12, 48, 24, 4,136, 24, 18, 6, ... - R. J. Mathar, Aug 10 2012

This is one of only two Lucas-type sequences whose 8th term is a square. The other one is A097705. - Michel Marcus, Dec 07 2012

Numerators of stationary probabilities for the M2/M/1 queue. In this queue, customers arrives in groups of 2. Intensity of arrival = 1. Service rate = 4. There is only one server and an infinite queue. - Igor Kleiner, Nov 02 2018

Number of 4-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020

From M. Eren Kesim, May 13 2021: (Start)

a(n) is equal to the number of n-step walks from a universal vertex to another (itself or the other) on the diamond graph. It is also equal to the number of (n+1)-step walks from vertex A to vertex B on the graph below.

B--C

| /|

|/ |

A--D

(End)

From Wolfdieter Lang, Jan 03 2024: (Start)

This sequence {a(n-1)}, with a(-1) = 0, appears in the formula for powers of phi17 := (1 + sqrt(17))/2 = A222132, the fundamental (integer) algebraic number of Q(sqrt(17)): phi17^n = A052923(n) + a(n-1)*phi17, for n >= 0.

Limit_{n->oo} a(n+1)/a(n) = phi17. (End)

Examples

			G.f. = 1 + x + 5*x^2 + 9*x^3 + 29*x^4 + 65*x^5 + 181*x^6 + 441*x^7 + 1165*x^8 + ...
		

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Ilya Amburg, Krishna Dasaratha, Laure Flapan, Thomas Garrity, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse, and Matthew Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239 [math.CO], 2015.
• Joerg Arndt, Matters Computational (The Fxtbook), pp.317-318.
• Jolanta Borowska and Lena Łacińska, Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix", J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for tridiagonal Toeplitz matrices a=1, b=2.
• Andrew Bremner and Nikos Tzanakis, Lucas sequences whose 8th term is a square, arXiv:math/0408371 [math.NT], 2004.
• Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 437
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 387, 389.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• A. G. Shannon and J. V. Leyendekkers, The Golden Ratio family and the Binet equation, Notes on Number Theory and Discrete Mathematics, Vol. 21, No. 2, (2015), 35-42.
• A. K. Whitford, Binet's formula generalized, Fib. Quart., 15 (1977), pp. 21, 24, 29.
• Paul Thomas Young, p-adic congruences for generalized Fibonacci sequences, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
• Index entries for linear recurrences with constant coefficients, signature (1,4).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

Cf. A006130, A015440, A026581, A026583, A026597, A026599, A052923, A097705, A102446, A063727, A344236, A344261.

Programs

GAP

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

Magma

[ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+4*Self(n-2): n in [1..40] ]; // Vincenzo Librandi, Aug 19 2011

Maple

A006131:=-1/(-1+z+4*z**2); # conjectured by Simon Plouffe in his 1992 dissertation
seq( simplify((2/I)^n*ChebyshevU(n, I/4)), n=0..30); # G. C. Greubel, Dec 26 2019

Mathematica

m = 16; f[n_] = Product[(1 + m*Cos[k*Pi/n]^2), {k, 1, Floor[(n - 1)/2]}]; Table[FullSimplify[ExpandAll[f[n]]], {n, 0, 15}]; N[%] (* Roger L. Bagula, Nov 21 2008 *)
a[n_]:=(MatrixPower[{{1,4},{1,0}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{1, 4}, {1, 1}, 29] (* Jean-François Alcover, Sep 25 2017 *)
Table[2^n*Fibonacci[n+1, 1/2], {n,0,30}] (* G. C. Greubel, Dec 26 2019 *)

PARI

a(n)=([0,1; 4,1]^n*[1;1])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

PARI

vector(31, n, (2/I)^(n-1)*polchebyshev(n-1, 2, I/4) ) \\ G. C. Greubel, Dec 26 2019

Python

def A006131_list(n):
    list = [1, 1] + [0] * (n - 2)
    for i in range(2, n):
        list[i] = list[i - 1] + 4 * list[i - 2]
    return list
print(A006131_list(29)) # M. Eren Kesim, Jul 19 2021

Sage

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

Formula

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

a(n) = (((1+sqrt(17))/2)^(n+1) - ((1-sqrt(17))/2)^(n+1))/sqrt(17).

a(n+1) = Sum_{k=0..ceiling(n/2)} 4^k*binomial(n-k, k). - Benoit Cloitre, Mar 06 2004

a(n) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)*(1+(-1)^(n-k))*2^(n-k)/2. - Paul Barry, Aug 28 2005

a(n) = A102446(n)/2. - Zerinvary Lajos, Jul 09 2008

a(n) = Sum_{k=0..n} A109466(n,k)*(-4)^(n-k). - Philippe Deléham, Oct 26 2008

a(n) = Product_{k=1..floor((n - 1)/2)} (1 + 16*cos(k*Pi/n)^2). - Roger L. Bagula, Nov 21 2008

Limiting ratio a(n+1)/a(n) is (1 + sqrt(17))/2 = 2.561552812... - Roger L. Bagula, Nov 21 2008

The fraction b(n) = a(n)/2^n satisfies b(n) = 1/2 b(n-1) + b(n-2); g.f. 1/(1-x/2-x^2); b(n) = (( (1+sqrt(17))/4 )^(n+1) - ( (1-sqrt(17))/4 )^(n+1))*2/sqrt(17). - Franklin T. Adams-Watters, Nov 30 2009

G.f.: G(0)/(2-x), where G(k) = 1 + 1/(1 - x*(17*k-1)/(x*(17*k+16) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013

G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + 4*x)/( x*(4*k+3 + 4*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 09 2013

G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(k+1 + 4*x)/( x*(k+3/2 + 4*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 14 2013

G.f.: 1 / (1 - x / (1 - 4*x / (1 + 4*x))). - Michael Somos, Sep 15 2013

a(n) = (Sum_{1<=k<=n+1, k odd} C(n+1,k)*17^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014

a(n) = 2^n*Fibonacci(n+1, 1/2) = (2/i)^n*ChebyshevU(n, i/4). - G. C. Greubel, Dec 26 2019

E.g.f.: exp(x/2)*(sqrt(17)*cosh(sqrt(17)*x/2) + sinh(sqrt(17)*x/2))/sqrt(17). - Stefano Spezia, Dec 27 2019

a(n) = A344236(n) + A344261(n). - M. Eren Kesim, May 13 2021

With an initial 0 prepended, the sequence [0, 1, 1, 5, 9, 29, 65, ...] satisfies the congruences a(n*p^k) == e*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where e = +1 for the primes p listed in A296938, e = 0 when p = 17, otherwise e = -1. - Peter Bala, Dec 28 2022

a(n) = A052923(n+2)/4. - Wolfdieter Lang, Jan 03 2024

From Peter Bala, Jun 27 2025: (Start)

The following products telescope:

Product_{k >= 0} (1 + 4^k/a(2*k+1)) = 1 + sqrt(17).

Product_{k >= 1} (1 - 4^k/a(2*k+1)) = 1/18 * (1 + sqrt(17)).

Product_{k >= 0} (1 + (-4)^k/a(2*k+1)) = (1/17) * (17 + sqrt(17)).

Product_{k >= 1} (1 - (-4)^k/a(2*k+1)) = (1/18) * (17 + sqrt(17)). (End)

Extensions

More terms from Roger L. Bagula, Sep 26 2006