|
%I M3788 #177 Jan 16 2024 04:45:37
%S 1,1,5,9,29,65,181,441,1165,2929,7589,19305,49661,126881,325525,
%T 833049,2135149,5467345,14007941,35877321,91909085,235418369,
%U 603054709,1544728185,3956947021,10135859761,25963647845,66507086889,170361678269
%N a(n) = a(n-1) + 4*a(n-2), a(0) = a(1) = 1.
%C 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 Equals INVERTi transform of A063727: (1, 2, 8, 24, 80, 256, 832, ...). - _Gary W. Adamson_, Aug 12 2010
%C 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 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 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 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 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 Number of 4-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C From _M. Eren Kesim_, May 13 2021: (Start)
%C 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 B--C
%C | /|
%C |/ |
%C A--D
%C (End)
%C From _Wolfdieter Lang_, Jan 03 2024: (Start)
%C 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 Limit_{n->oo} a(n+1)/a(n) = phi17. (End)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006131/b006131.txt">Table of n, a(n) for n = 0..1000</a>
%H 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 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.317-318.
%H J. Borowska, L. Lacinska, <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 A. Bremner and N. 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 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 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=437">Encyclopedia of Combinatorial Structures 437</a>
%H 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 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 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H 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 A. K. Whitford, <a href="http://www.fq.math.ca/Scanned/15-1/whitford-a.pdf">Binet's formula generalized</a>, Fib. Quart., 15 (1977), pp. 21, 24, 29.
%H Paul Thomas Young, <a href="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 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,4).
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%F G.f.: 1/(1 - x - 4*x^2).
%F a(n) = (((1+sqrt(17))/2)^(n+1) - ((1-sqrt(17))/2)^(n+1))/sqrt(17).
%F a(n+1) = Sum_{k=0..ceiling(n/2)} 4^k*binomial(n-k, k). - _Benoit Cloitre_, Mar 06 2004
%F 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 a(n) = A102446(n)/2. - _Zerinvary Lajos_, Jul 09 2008
%F a(n) = Sum_{k=0..n} A109466(n,k)*(-4)^(n-k). - _Philippe Deléham_, Oct 26 2008
%F a(n) = Product_{k=1..floor((n - 1)/2)} (1 + 16*cos(k*Pi/n)^2). - _Roger L. Bagula_, Nov 21 2008
%F Limiting ratio a(n+1)/a(n) is (1 + sqrt(17))/2 = 2.561552812... - _Roger L. Bagula_, Nov 21 2008
%F 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 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 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 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 G.f.: 1 / (1 - x / (1 - 4*x / (1 + 4*x))). - _Michael Somos_, Sep 15 2013
%F 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 a(n) = 2^n*Fibonacci(n+1, 1/2) = (2/i)^n*ChebyshevU(n, i/4). - _G. C. Greubel_, Dec 26 2019
%F 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 a(n) = A344236(n) + A344261(n). - _M. Eren Kesim_, May 13 2021
%F 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 a(n) = A052923(n+2)/4. - _Wolfdieter Lang_, Jan 03 2024
%e 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:=-1/(-1+z+4*z**2); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%p seq( simplify((2/I)^n*ChebyshevU(n, I/4)), n=0..30); # _G. C. Greubel_, Dec 26 2019
%t 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 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 LinearRecurrence[{1, 4}, {1, 1}, 29] (* _Jean-François Alcover_, Sep 25 2017 *)
%t Table[2^n*Fibonacci[n+1, 1/2], {n,0,30}] (* _G. C. Greubel_, Dec 26 2019 *)
%o (Sage) [lucas_number1(n,1,-4) for n in range(1, 30)] # _Zerinvary Lajos_, Apr 22 2009
%o (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 (PARI) a(n)=([0,1; 4,1]^n*[1;1])[1,1] \\ _Charles R Greathouse IV_, Oct 03 2016
%o (PARI) vector(31, n, (2/I)^(n-1)*polchebyshev(n-1, 2, I/4) ) \\ _G. C. Greubel_, Dec 26 2019
%o (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 (Python)
%o def A006131_list(n):
%o list = [1, 1] + [0] * (n - 2)
%o for i in range(2, n):
%o list[i] = list[i - 1] + 4 * list[i - 2]
%o return list
%o print(A006131_list(29)) # _M. Eren Kesim_, Jul 19 2021
%Y Cf. A006130, A015440, A026581, A026583, A026597, A026599, A052923, A097705, A102446, A063727, A344236, A344261.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Roger L. Bagula_, Sep 26 2006
|
