OFFSET
1,3
COMMENTS
For bit strings of length 1,2,3,.. the sequence gives the number of strings of that length that contain at least one '11' not flanked by 1's; i.e., an occurrence of '0110' is OK; an occurrence of '0111' does not count. Thus the strings '0110011' and '0110111' are counted but '0111000' is not because '11' does not occur by itself.
FORMULA
a(n) = 2*a(n-1) + 2^n-3 - a(n-3) - 2^n-4 + a(n-4).
G.f.: (1 - x)^2*x^2/((1-2*x)*(1 - 2*x + x^3 -x^4)). - Geoffrey Critzer, Jan 23 2014
EXAMPLE
a(5) = 11 because we have: 00011, 00110, 01011, 01100, 01101, 10011, 10110, 11000, 11001, 11010, 11011. - Geoffrey Critzer, Jan 23 2014
MATHEMATICA
nn=30; r=Solve[{s==1+x s+x c+x a, a==x s, b==x a, c==x b+x c, d==x b+2x d}, {s, a, b, c, d}]; Drop[Flatten[CoefficientList[Series[b+d/.r, {x, 0, nn}], x]], 1] (* Geoffrey Critzer, Jan 23 2014 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Oskars Rieksts (rieksts(AT)kutztown.edu), May 13 2010
EXTENSIONS
Better name and more terms from Geoffrey Critzer, Jan 23 2014
STATUS
approved