A098590 a(n) = 4^n for n = 0..3; for n > 3, a(n) = 4*a(n-1) + a(n-4).

1, 4, 16, 64, 257, 1032, 4144, 16640, 66817, 268300, 1077344, 4326016, 17370881, 69751824, 280084640, 1124664576, 4516029185, 18133868564, 72815558896, 292386900160, 1174063629825, 4714388387864, 18930369110352, 76013863341568

Offset: 0

Author

Paul Barry, Sep 16 2004

Keywords

• easy
• nonn

Comments

a(n) equals the number of n-length words on {0,1,2,3,4} such that 0 appears only in a run which length is a multiple of 4. - Milan Janjic, Feb 17 2015

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (4,0,0,1).

Crossrefs

Cf. A052541.

Programs

Magma

I:=[0,1,4,16]; [n le 4 select I[n] else 4*Self(n-1) +Self(n-4): n in [1..30]]; // G. C. Greubel, Feb 03 2018

Maple

K:=1/(1+4*z-z^4): Kser:=series(K, z=0, 30): seq(abs(coeff(Kser, z, n)), n= 0..23); # Zerinvary Lajos, Nov 08 2007

Mathematica

CoefficientList[Series[1/(1 - 4*x - x^4), {x, 0, 25}], x] (* Zerinvary Lajos, Mar 29 2007 *)
LinearRecurrence[{4,0,0,1},{0,1,4,16},30] (* Harvey P. Dale, Jul 22 2014 *)

PARI

x='x+O('x^30); Vec(1/(1-4*x-x^4)) \\ G. C. Greubel, Feb 03 2018

Formula

G.f.: 1/(1-4*x-x^4).

a(n) = Sum_{k=0..floor(n/3)} binomial(n-3*k, k) * 4^(n-4*k).