OFFSET
0,2
COMMENTS
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-1).
FORMULA
G.f.: (x+1)*(x^2-x+1) / (x^5-2*x^4+x^3-2*x+1).
a(n) = 2^n if n<5, and a(n) = 2*(a(n-1)+a(n-4)) -a(n-3) -a(n-5) otherwise.
EXAMPLE
a(6) = 60 because among the 2^6 = 64 binary words of length 6 only 4, namely 001101, 011010, 011011 and 101101 contain the subword 01101.
MAPLE
a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [-1, 2, -1, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);
MATHEMATICA
CoefficientList[Series[(x + 1)*(x^2 - x + 1)/(x^5 - 2*x^4 + x^3 - 2*x + 1), {x, 0, 40}], x] (* Wesley Ivan Hurt, Apr 28 2017 *)
LinearRecurrence[{2, 0, -1, 2, -1}, {1, 2, 4, 8, 16}, 40] (* Harvey P. Dale, Sep 17 2017 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 14 2012
STATUS
approved