A052923 -id:A052923 - cp's OEIS frontend

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

N. J. A. Sloane

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)

			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 + ...

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

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.

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

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

[ 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

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

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 *)

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

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

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

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

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)

More terms from Roger L. Bagula, Sep 26 2006

A222132 Decimal expansion of sqrt(4 + sqrt(4 + sqrt(4 + sqrt(4 + ... )))).

Original entry on oeis.org

2, 5, 6, 1, 5, 5, 2, 8, 1, 2, 8, 0, 8, 8, 3, 0, 2, 7, 4, 9, 1, 0, 7, 0, 4, 9, 2, 7, 9, 8, 7, 0, 3, 8, 5, 1, 2, 5, 7, 3, 5, 9, 9, 6, 1, 2, 6, 8, 6, 8, 1, 0, 2, 1, 7, 1, 9, 9, 3, 1, 6, 7, 8, 6, 5, 4, 7, 4, 7, 7, 1, 7, 3, 1, 6, 8, 8, 1, 0, 7, 9, 6, 7, 9, 3, 9, 3, 1, 8, 2, 5, 4, 0, 5, 3, 4, 2, 1, 4, 8, 3, 4, 2, 2, 7

Offset: 1

Jaroslav Krizek, Feb 08 2013

Sequence with a(1) = 1 is decimal expansion of sqrt(4 - sqrt(4 - sqrt(4 - sqrt(4 - ... )))) = A222133.
Because 17 == 1 (mod 4), the basis for integers in the real quadratic number field K(sqrt(17)) is <1, omega(17)>, where omega(17) = (1 + sqrt(17))/2. - Wolfdieter Lang, Feb 10 2020
This is the positive root of the polynomial x^2 - x - 4, with negative root -A222133. - Wolfdieter Lang, Dec 10 2022
It is the spectral radius of the diamond graph (see Seeger and Sossa, 2023). - Stefano Spezia, Sep 19 2023
c^n = A006131(n) + A006131(n-1) * d, where c = (1 + sqrt(17))/2 and d = (-1 + sqrt(17))/2. - Gary W. Adamson, Nov 25 2023
c^n = A052923(n) + A006131(n-1) * c. Also for negative n. - Wolfdieter Lang, Nov 27 2023
The effective degree of maximal entropy random walk on the barred-square graph (see Burda et al.). - Stefano Spezia, Feb 07 2025

			2.561552812808830274910704...

J. Burda, J. Duda, J. M. Luck, and B. Waclaw, The Various Facets of Random Walk Entropy, Acta Phys. Pol. B 41, 949-987 (2010). See pp. 964, 969.
Alberto Seeger and David Sossa, Infinite families of connected graphs with equal spectral radius, Australas. J. Combin. 87 (2) (2023), 258-276. See pp. 260 and 263.

Cf. A222133, A178255, A082486.

Cf. A006131, A052923.

Digits:=140:
evalf((sqrt(17)+1)/2);  # Alois P. Heinz, Sep 19 2023

Mathematica
```
RealDigits[(1 + Sqrt[17])/2, 10, 130]
```

Closed form: (sqrt(17) + 1)/2 = A178255 - 1 = A082486 - 2.

sqrt(4 + sqrt(4 + sqrt(4 + sqrt(4 + ... )))) - 1 = sqrt(4 - sqrt(4 - sqrt(4 - sqrt(4 - ... )))). See A222133.

A026581 Expansion of (1 + 2x) / (1 - x - 4x^2).

Original entry on oeis.org

1, 3, 7, 19, 47, 123, 311, 803, 2047, 5259, 13447, 34483, 88271, 226203, 579287, 1484099, 3801247, 9737643, 24942631, 63893203, 163663727, 419236539, 1073891447, 2750837603, 7046403391, 18049753803, 46235367367, 118434382579, 303375852047, 777113382363

Offset: 0

Clark Kimberling

T(n,0) + T(n,1) + ... + T(n,2n), T given by A026568.
Row sums of Riordan array ((1+2x)/(1+x),x(1+2x)/(1+x)). Binomial transform is A055099. - Paul Barry, Jun 26 2008
Equals row sums of triangle A153341. - Gary W. Adamson, Dec 24 2008
Also, the number of walks of length n starting at vertex 0 in the graph with 4 vertices and edges {{0,1}, {0,2}, {0,3}, {1,2}, {2,3}}. - Sean A. Irvine, Jun 02 2025

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,4).

Cf. A006131, A026568, A026583, A026597, A026599, A052923, A055099.

Cf. A153341. - Gary W. Adamson, Dec 24 2008

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

I:=[1,3]; [n le 2 select I[n] else Self(n-1) +4*Self(n-2): n in [1..30]]; // G. C. Greubel, Aug 03 2019

CoefficientList[Series[(1+2x)/(1-x-4x^2),{x,0,30}],x] (* or *) LinearRecurrence[{1,4},{1,3},30] (* Harvey P. Dale, Aug 04 2015 *)

Vec((1+2*x)/(1-x-4*x^2) + O(x^30)) \\ Colin Barker, Dec 22 2016

((1+2*x)/(1-x-4*x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Aug 03 2019

G.f.: (1 + 2*x) / (1 - x - 4*x^2).
a(n) = a(n-1) + 4*a(n-2), n>1.
a(n) = 2*A006131(n-1) + A006131(n), n>0.
a(n) = (2^(-1-n)*((1-sqrt(17))^n*(-5+sqrt(17)) + (1+sqrt(17))^n*(5+sqrt(17))))/sqrt(17). - Colin Barker, Dec 22 2016

Edited by Ralf Stephan, Jul 20 2013

The negative root is -(A189038 - 1) = -0.6403882032... .

c^n = A052923(-n) + A006131(-(n+1))*phi17, for n >= 0, with phi17 = A222132 = (1 + sqrt(17))/2, A052923(-n) = -(-2*i)^(-n)*S(-(n+2), i/2) = (i/2)^n*S(n, i/2), with i = sqrt(-1), and A006131(-(n+1)) = A052923(-n+1)/4 = -(i/2)^(n+1)*S(n-1, i/2), with the S-Chebyshev polynomials (see A049310), and S(-n, x) = -S(n-2, x), for n >= 1. - Wolfdieter Lang, Jan 04 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A222132 Decimal expansion of sqrt(4 + sqrt(4 + sqrt(4 + sqrt(4 + ... )))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A026581 Expansion of (1 + 2*x) / (1 - x - 4*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A358945 Decimal expansion of the positive root of 4*x^2 + x - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A026581 Expansion of (1 + 2x) / (1 - x - 4x^2).