OFFSET
0,4
COMMENTS
We set a(2) = 1 by convention; there is one string of length 2 which has two consecutive 1's, namely 11. This also makes various formulas simpler.
For n>=3, a(n) = 2^n - the sum of all terms in the (n-3)rd power of the 4 X 4 matrix [[1 1 0 0] [0 0 1 0] [0 0 0 1] [1 1 0 0]] because this matrix represents the transitions from the state where the last three bits are 000, 001, 010, 100 to the state after the next bit, always avoiding two 1's out of the last three bits. - Joshua Zucker, Aug 04 2006
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,1,-2).
FORMULA
a(n) = 3*2^(n-3) + a(n-1) + a(n-3) for n >= 3. - Tanya Khovanova, Aug 22 2006
From R. J. Mathar, Oct 03 2011: (Start)
G.f.: (x^3 + x^2)/(2*x^4 - x^3 + 2*x^2 - 3*x + 1).
G.f.: x^2 * (x+1)/((2*x-1)*(x^3+x-1)).
a(n) = 2^n - A000930(n+2). (End)
EXAMPLE
a(4) = 10 because we have: 0011, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111. - Geoffrey Critzer, Jan 19 2014
MATHEMATICA
nn=31; r=Solve[{s==1+x s+x b, a==x s, b==x a, c==x a+x b+2x c}, {s, a, b, c}]; CoefficientList[Series[c/.r, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 19 2014 *)
LinearRecurrence[{3, -2, 1, -2}, {0, 0, 1, 4}, 40] (* Harvey P. Dale, Dec 15 2014 *)
PROG
(PARI) x='x+O('x^50); concat([0, 0], Vec((x^3 + x^2)/(2*x^4 - x^3 + 2*x^2 - 3*x + 1))) \\ G. C. Greubel, May 02 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Tanya Khovanova, May 10 2006
EXTENSIONS
More terms from Joshua Zucker, Aug 04 2006
Edited by Franklin T. Adams-Watters, Sep 30 2011
STATUS
approved