cp's OEIS Frontend

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

%I A006131 M3788 #194 Jul 11 2025 09:06:45
%S A006131 1,1,5,9,29,65,181,441,1165,2929,7589,19305,49661,126881,325525,
%T A006131 833049,2135149,5467345,14007941,35877321,91909085,235418369,
%U A006131 603054709,1544728185,3956947021,10135859761,25963647845,66507086889,170361678269
%N A006131 a(n) = a(n-1) + 4*a(n-2), a(0) = a(1) = 1.
%C A006131 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
%C A006131 Equals INVERTi transform of A063727: (1, 2, 8, 24, 80, 256, 832, ...). - _Gary W. Adamson_, Aug 12 2010
%C A006131 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
%C A006131 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
%C A006131 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
%C A006131 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
%C A006131 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
%C A006131 Number of 4-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C A006131 From _M. Eren Kesim_, May 13 2021: (Start)
%C A006131 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.
%C A006131     B--C
%C A006131     | /|
%C A006131     |/ |
%C A006131     A--D
%C A006131 (End)
%C A006131 From _Wolfdieter Lang_, Jan 03 2024: (Start)
%C A006131 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.
%C A006131 Limit_{n->oo} a(n+1)/a(n) = phi17. (End)
%D A006131 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006131 Vincenzo Librandi, <a href="/A006131/b006131.txt">Table of n, a(n) for n = 0..1000</a>
%H A006131 Ilya Amburg, Krishna Dasaratha, Laure Flapan, Thomas Garrity, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse, and Matthew Stoffregen, <a href="http://arxiv.org/abs/1509.05239">Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences</a>, arXiv:1509.05239 [math.CO], 2015.
%H A006131 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.317-318.
%H A006131 Jolanta Borowska and Lena Łacińska, <a href="https://doi.org/10.17512/jamcm.2014.4.03">Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix"</a>, J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for tridiagonal Toeplitz matrices a=1, b=2.
%H A006131 Andrew Bremner and Nikos Tzanakis, <a href="https://arxiv.org/abs/math/0408371">Lucas sequences whose 8th term is a square</a>, arXiv:math/0408371 [math.NT], 2004.
%H A006131 Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H A006131 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=437">Encyclopedia of Combinatorial Structures 437</a>
%H A006131 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H A006131 Thor Martinsen, <a href="https://doi.org/10.7546/nntdm.2025.31.2.370-389">Non-Fisherian generalized Fibonacci numbers</a>, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 387, 389.
%H A006131 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A006131 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A006131 A. G. Shannon and J. V. Leyendekkers, <a href="http://nntdm.net/volume-21-2015/number-2/35-42/">The Golden Ratio family and the Binet equation</a>, Notes on Number Theory and Discrete Mathematics, Vol. 21, No. 2, (2015), 35-42.
%H A006131 A. K. Whitford, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/15-1/whitford-a.pdf">Binet's formula generalized</a>, Fib. Quart., 15 (1977), pp. 21, 24, 29.
%H A006131 Paul Thomas Young, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/32-1/young.pdf">p-adic congruences for generalized Fibonacci sequences</a>, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
%H A006131 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,4).
%H A006131 <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%F A006131 G.f.: 1/(1 - x - 4*x^2).
%F A006131 a(n) = (((1+sqrt(17))/2)^(n+1) - ((1-sqrt(17))/2)^(n+1))/sqrt(17).
%F A006131 a(n+1) = Sum_{k=0..ceiling(n/2)} 4^k*binomial(n-k, k). - _Benoit Cloitre_, Mar 06 2004
%F A006131 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
%F A006131 a(n) = A102446(n)/2. - _Zerinvary Lajos_, Jul 09 2008
%F A006131 a(n) = Sum_{k=0..n} A109466(n,k)*(-4)^(n-k). - _Philippe Deléham_, Oct 26 2008
%F A006131 a(n) = Product_{k=1..floor((n - 1)/2)} (1 + 16*cos(k*Pi/n)^2). - _Roger L. Bagula_, Nov 21 2008
%F A006131 Limiting ratio a(n+1)/a(n) is (1 + sqrt(17))/2 = 2.561552812... - _Roger L. Bagula_, Nov 21 2008
%F A006131 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
%F A006131 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
%F A006131 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
%F A006131 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
%F A006131 G.f.: 1 / (1 - x / (1 - 4*x / (1 + 4*x))). - _Michael Somos_, Sep 15 2013
%F A006131 a(n) = (Sum_{1<=k<=n+1, k odd} C(n+1,k)*17^((k-1)/2))/2^n. - _Vladimir Shevelev_, Feb 05 2014
%F A006131 a(n) = 2^n*Fibonacci(n+1, 1/2) = (2/i)^n*ChebyshevU(n, i/4). - _G. C. Greubel_, Dec 26 2019
%F A006131 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
%F A006131 a(n) = A344236(n) + A344261(n). - _M. Eren Kesim_, May 13 2021
%F A006131 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
%F A006131 a(n) = A052923(n+2)/4. - _Wolfdieter Lang_, Jan 03 2024
%F A006131 From _Peter Bala_, Jun 27 2025: (Start)
%F A006131 The following products telescope:
%F A006131 Product_{k >= 0} (1 + 4^k/a(2*k+1)) = 1 + sqrt(17).
%F A006131 Product_{k >= 1} (1 - 4^k/a(2*k+1)) = 1/18 * (1 + sqrt(17)).
%F A006131 Product_{k >= 0} (1 + (-4)^k/a(2*k+1)) = (1/17) * (17 + sqrt(17)).
%F A006131 Product_{k >= 1} (1 - (-4)^k/a(2*k+1)) = (1/18) * (17 + sqrt(17)). (End)
%e A006131 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 + ...
%p A006131 A006131:=-1/(-1+z+4*z**2); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%p A006131 seq( simplify((2/I)^n*ChebyshevU(n, I/4)), n=0..30); # _G. C. Greubel_, Dec 26 2019
%t A006131 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 *)
%t A006131 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 *)
%t A006131 LinearRecurrence[{1, 4}, {1, 1}, 29] (* _Jean-François Alcover_, Sep 25 2017 *)
%t A006131 Table[2^n*Fibonacci[n+1, 1/2], {n,0,30}] (* _G. C. Greubel_, Dec 26 2019 *)
%o A006131 (Sage) [lucas_number1(n,1,-4) for n in range(1, 30)] # _Zerinvary Lajos_, Apr 22 2009
%o A006131 (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
%o A006131 (PARI) a(n)=([0,1; 4,1]^n*[1;1])[1,1] \\ _Charles R Greathouse IV_, Oct 03 2016
%o A006131 (PARI) vector(31, n, (2/I)^(n-1)*polchebyshev(n-1, 2, I/4) ) \\ _G. C. Greubel_, Dec 26 2019
%o A006131 (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
%o A006131 (Python)
%o A006131 def A006131_list(n):
%o A006131     list = [1, 1] + [0] * (n - 2)
%o A006131     for i in range(2, n):
%o A006131         list[i] = list[i - 1] + 4 * list[i - 2]
%o A006131     return list
%o A006131 print(A006131_list(29)) # _M. Eren Kesim_, Jul 19 2021
%Y A006131 Cf. A006130, A015440, A026581, A026583, A026597, A026599, A052923, A097705, A102446, A063727, A344236, A344261.
%K A006131 nonn,easy
%O A006131 0,3
%A A006131 _N. J. A. Sloane_
%E A006131 More terms from _Roger L. Bagula_, Sep 26 2006