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

13, 21, 33, 53, 85, 137, 221, 357, 577, 933, 1509, 2441, 3949, 6389, 10337, 16725, 27061, 43785, 70845, 114629, 185473, 300101, 485573, 785673, 1271245, 2056917, 3328161, 5385077, 8713237, 14098313, 22811549, 36909861, 59721409, 96631269

Offset

4,1

Links

R. H. Hardin, Table of n, a(n) for n = 4..500

Martin Griffiths, On a Matrix Arising from a Family of Iterated Self-Compositions, Journal of Integer Sequences, 18 (2015), #15.11.8.

Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Formula

G.f.: -x^4*(-13 + 5*x + 9*x^2) / ((x - 1)*(x^2 + x - 1)). - R. J. Mathar, Jan 19 2011

a(n) = 4*Fibonacci(n) + 1. - Bruno Berselli, Jul 26 2017

From Colin Barker, Jul 26 2017: (Start)

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

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

(End)

Prog

(PARI) Vec(-x^4*(-13 + 5*x + 9*x^2) / ((x - 1)*(x^2 + x - 1)) + O(x^60)) \\ Colin Barker, Jul 26 2017
(Python)
from sympy import fibonacci
def a(n): return 4*fibonacci(n) + 1
print([a(n) for n in range(4, 101)]) # Indranil Ghosh, Jul 26 2017

Crossrefs

Sequence in context: A164488 A164436 A164498 * A164447 A057200 A164454

Adjacent sequences: A164482 A164483 A164484 * A164486 A164487 A164488

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved