A164395 Number of binary strings of length n with no substrings equal to 0001 or 0101.

1, 2, 4, 8, 14, 24, 42, 72, 122, 208, 354, 600, 1018, 1728, 2930, 4968, 8426, 14288, 24226, 41080, 69658, 118112, 200274, 339592, 575818, 976368, 1655554, 2807192, 4759930, 8071040, 13685426, 23205288, 39347370, 66718224, 113128802, 191823544

Offset: 0

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn

Links

• R. H. Hardin, Table of n, a(n) for n = 0..500
• Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-2).

Programs

Mathematica

LinearRecurrence[{2,-1,2,-2}, {1, 2, 4, 8}, 50] (* G. C. Greubel, Sep 18 2017 *)

PARI

Vec((1 + x^2)/((1 - x)*(1 - x - 2*x^3)) + O(x^40)) \\ G. C. Greubel, Sep 18 2017

Formula

a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - 2*a(n-4). - Andrew Howroyd, Feb 14 2018

G.f.: (1 + x^2)/((1 - x)*(1 - x - 2*x^3)). - R. J. Mathar, Dec 01 2011

Extensions

a(0)-a(3) prepended by Andrew Howroyd, Feb 14 2018