login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006131 a(n) = a(n-1) + 4*a(n-2), a(0) = a(1) = 1.
(Formerly M3788)
38
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Length-n strings 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

REFERENCES

A. G. Shannon, J. V. Leyendekkers The Golden Ratio family and the Binet equation, Notes on Number Theory and Discrete Mathematics, Vol. 21, 2015, No. 2, 35-42.

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, 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

A. Bremner and N. Tzanakis, Lucas sequences whose 8th term is a square

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 437

M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

A. K. Whitford, Binet's formula generalized, Fib. Quart., 15 (1977), pp. 21, 24, 29.

Index entries for linear recurrences with constant coefficients, signature (1,4).

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, ceil(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(0<=k<=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

EXAMPLE

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

MAPLE

A006131:=-1/(-1+z+4*z**2); # conjectured by Simon Plouffe in his 1992 dissertation

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

PROG

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

(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

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

CROSSREFS

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

Sequence in context: A280487 A191013 A193487 * A270595 A242329 A214902

Adjacent sequences:  A006128 A006129 A006130 * A006132 A006133 A006134

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Roger L. Bagula, Sep 26 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 20 04:05 EST 2017. Contains 294959 sequences.