A164413 Number of binary strings of length n with no substrings equal to 0000, 0001 or 1001.

1, 2, 4, 8, 13, 22, 36, 58, 94, 152, 246, 398, 644, 1042, 1686, 2728, 4414, 7142, 11556, 18698, 30254, 48952, 79206, 128158, 207364, 335522, 542886, 878408, 1421294, 2299702, 3720996, 6020698, 9741694, 15762392, 25504086, 41266478, 66770564, 108037042

Offset: 0

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn
• easy

Comments

Essentially the same as A022112. - R. J. Mathar, Nov 30 2011

Links

• David A. Corneth, Table of n, a(n) for n = 0..1999 (terms n = 4..500 from R. H. Hardin)
• Index entries for linear recurrences with constant coefficients, signature (1,1).

Programs

PARI

Vec(-(x^2+1)*(x^2-x+1)*(x+1)^2/(x^2+x-1) + O(x^50)) \\ Colin Barker, Oct 27 2017

PARI

first(n) = {my(start = [1, 2, 4, 8, 13, 22, 36]); if(n <= 7, return(vector(n+1, i, start[i]))); res = concat(start, vector(n-7)); for(i=8, n,
res[i] = res[i-1] + res[i-2]); res} \\ David A. Corneth, Oct 27 2017

Formula

From Colin Barker, Oct 27 2017: (Start)

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

a(n) = 2*(((1 - sqrt(5))/2)^n + ((1 + sqrt(5))/2)^n) for n>4.

a(n) = a(n-1) + a(n-2) for n>6.

(End)