A008998 a(n) = 2*a(n-1) + a(n-3), with a(0)=1 and a(1)=2.

1, 2, 4, 9, 20, 44, 97, 214, 472, 1041, 2296, 5064, 11169, 24634, 54332, 119833, 264300, 582932, 1285697, 2835694, 6254320, 13794337, 30424368, 67103056, 148000449, 326425266, 719953588, 1587907625, 3502240516, 7724434620, 17036776865, 37575794246

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

A transform of A000079 under the mapping g(x)->(1/(1-x^3))g(x/(1-x^3)). - Paul Barry, Oct 20 2004

The binomial transform yields 1,3,9,..., i.e., A049220 without the leading zeros. - R. J. Mathar, May 15 2008

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

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

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

For x the real root of x^3 - 2*x^2 - 1 from A356035, then x^n = a(n-4)*x^2 + a(n-2)*x + a(n-3). - Greg Dresden and Qianhuai He, Jul 01 2025

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 452
• B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.
• Index entries for linear recurrences with constant coefficients, signature (2,0,1).

Crossrefs

Cf. A077852, A077926. Partial sums of A052980.

Programs

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

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

Maple

A008998 := proc(n) option remember; if n <= 2 then 2^n else 2*procname(n-1) +procname(n-3); fi; end proc;

Mathematica

LinearRecurrence[{2, 0, 1}, {1, 2, 4}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 13 2012 *)

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

Sage

def A008998_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/(1-2*x-x^3) ).list()
A008998_list(40) # G. C. Greubel, Feb 14 2020

Formula

a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k, k)*2^(n-3k). - Paul Barry, Oct 20 2004

O.g.f.: 1/(1-2*x-x^3). - R. J. Mathar, May 15 2008

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

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

a(n) = Sum_{k=0..n} A052980(n). - Greg Dresden, May 28 2020