The OEIS is supported by the many generous donors to the OEIS Foundation. 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) 45
 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 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) 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. A. Bremner and N. 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 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; 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. 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..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 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 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 *) PROG (Sage) [lucas_number1(n, 1, -4) for n in range(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 (PARI) vector(31, n, (2/I)^(n-1)*polchebyshev(n-1, 2, I/4) ) \\ G. C. Greubel, Dec 26 2019 (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 (Python) def A006131_list(n):     list = [1, 1] +  * (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 CROSSREFS Cf. A006130, A015440, A026581, A026583, A026597, A026599, A052923, A097705, A102446, A063727, A344236, A344261. Sequence in context: A280487 A191013 A193487 * A352008 A270595 A303988 Adjacent sequences:  A006128 A006129 A006130 * A006132 A006133 A006134 KEYWORD nonn,easy AUTHOR 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 7 07:33 EDT 2022. Contains 357270 sequences. (Running on oeis4.)