OFFSET
0,5
COMMENTS
Recurrence formula given below, a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)) based on following recursive construction: To a string of length (n-1) containing 000 add any of {0,1,2}. To a string of length (n-4) NOT containing 000, add 1000 or 2000. These two operations result in the two terms of the formula.
LINKS
Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4,-4,-6).
FORMULA
a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)).
G.f.: x^3/(1 - 5*x + 4*x^2 + 4*x^3 +6*x^4). - Geoffrey Critzer, Jan 14 2014
EXAMPLE
For n = 3, the only string is 000.
For n = 4, the 5 strings are: 0000,0001,0002,1000,2000.
For n = 5, there are: 1 with 5 0's, 12 with 4 0's, and 8 with just 3; total 21.
MATHEMATICA
t = {0, 0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 4) - t[[-4]])], {n, 4, 30}]; t (* T. D. Noe, Nov 11 2013 *)
(* or *)
nn=28; r=Solve[{s==2x s+2x a+2x b+1, a==x s, b==x a, c==3x c+x b}, {s, a, b, c}]; CoefficientList[Series[c/.r, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 14 2014 *)
CoefficientList[Series[x^3/(1-5x+4x^2+4x^3+6x^4), {x, 0, 40}], x] (* or *) LinearRecurrence[{5, -4, -4, -6}, {0, 0, 0, 1}, 40] (* Harvey P. Dale, Jul 27 2021 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Toby Gottfried, Nov 09 2013
STATUS
approved