|
%I #73 Sep 08 2022 08:44:37
%S 1,2,4,9,20,44,97,214,472,1041,2296,5064,11169,24634,54332,119833,
%T 264300,582932,1285697,2835694,6254320,13794337,30424368,67103056,
%U 148000449,326425266,719953588,1587907625,3502240516,7724434620,17036776865,37575794246
%N a(n) = 2*a(n-1) + a(n-3), with a(0)=1 and a(1)=2.
%C A transform of A000079 under the mapping g(x)->(1/(1-x^3))g(x/(1-x^3)). - _Paul Barry_, Oct 20 2004
%C The binomial transform yields 1,3,9,..., i.e., A049220 without the leading zeros. - _R. J. Mathar_, May 15 2008
%C a(n-3) is the top left entry of the n-th power of the 3 X 3 matrix [0, 0, 1; 1, 1, 1; 0, 1, 1] or of the 3 X 3 matrix [0, 1, 0; 0, 1, 1; 1, 1, 1]. - _R. J. Mathar_, Feb 03 2014
%C a(n) equals the number of n-length words on {0,1,2} such that 0 appears only in a run which length is a multiple of 3. - _Milan Janjic_, Feb 17 2015
%C a(n) is the number of ways to fill a 1 X n strip of tiles, using only trominos, of length 3, and squares which can be chosen to have one of two possible colors. - _Michael Tulskikh_, Feb 12 2020
%H Vincenzo Librandi, <a href="/A008998/b008998.txt">Table of n, a(n) for n = 0..200</a>
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=452">Encyclopedia of Combinatorial Structures 452</a>
%H B. Rittaud, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Rittaud2/rittaud11.html">On the Average Growth of Random Fibonacci Sequences</a>, Journal of Integer Sequences, 10 (2007), Article 07.2.4.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,1).
%F a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k, k)*2^(n-3k). - _Paul Barry_, Oct 20 2004
%F O.g.f.: 1/(1-2*x-x^3). - _R. J. Mathar_, May 15 2008
%F O.g.f.: exp( Sum_{n>=1} ( (1 + sqrt(1+x))^n + (1 - sqrt(1+x))^n ) * x^n/n ). - _Paul D. Hanna_, Dec 21 2012
%F G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+2 + x^2)/( x*(4*k+4 + x^2) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Aug 30 2013
%F a(n) = Sum_{k=0..n} A052980(n). - _Greg Dresden_, May 28 2020
%p A008998 := proc(n) option remember; if n <= 2 then 2^n else 2*procname(n-1) +procname(n-3); fi; end proc;
%t LinearRecurrence[{2, 0, 1}, {1, 2, 4}, 40] (* _Vladimir Joseph Stephan Orlovsky_, Feb 13 2012 *)
%o (Magma) [ n eq 1 select 1 else n eq 2 select 2 else n eq 3 select 4 else 2*Self(n-1)+Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Aug 21 2011
%o (PARI) {a(n)=polcoeff(exp(sum(m=1,n+1,((1+sqrt(1+x+x*O(x^n)))^m + (1-sqrt(1+x+x*O(x^n)))^m)*x^m/m)),n)} /* _Paul D. Hanna_, Dec 21 2012 */
%o (Sage)
%o def A008998_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( 1/(1-2*x-x^3) ).list()
%o A008998_list(40) # _G. C. Greubel_, Feb 14 2020
%o (GAP) a:=[1,2,4];; for n in [4..40] do a[n]:=2*a[n-1]+a[n-3]; od; a; # _G. C. Greubel_, Feb 14 2020
%Y Cf. A077852, A077926. Partial sums of A052980.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
|
