[seqfan] recurrences for pattern avoiding binary strings A164387 to A164494

[Richard Mathar]

All sequences below, counting binary numbers w/o specified fixed substrings,
seem to have linear recurrences - well known I presume but I have no proof
(so I'll not try to include them in the index of the linear recurrences):

A164387 a(n)= +a(n-1) +a(n-2) +a(n-4) -a(n-5)
A164388 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-5)
A164389 a(n)= +a(n-1) +2*a(n-3) +a(n-4)
A164390 a(n)= +a(n-1) +a(n-2) +a(n-4) +a(n-6)
A164391 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-5) -a(n-6)
A164392 a(n)= +2*a(n-1) -a(n-3) +a(n-4) -a(n-5)
A164393 a(n)= +2*a(n-1) -2*a(n-4) +a(n-5)
A164394 a(n)= +2*a(n-1) -a(n-2) +a(n-3)
A164395 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -2*a(n-4)
A164396 a(n)= +2*a(n-1) -a(n-3) +a(n-5) -a(n-6)
A164397 a(n)= +2*a(n-1) -2*a(n-4) +a(n-6)
A164398 a(n)= +2*a(n-1) -a(n-4)
A164399 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -2*a(n-4)
A164400 a(n)= +2*a(n-1) -2*a(n-4) +a(n-5)
A164401 a(n)= +2*a(n-1) -a(n-2) +a(n-3) +a(n-6)
A164402 a(n)= +2*a(n-1) -2*a(n-3) +2*a(n-4)
A164403 a(n)= +2*a(n-1) -a(n-3) +a(n-5)
A164404 a(n)= +2*a(n-1) -2*a(n-3) +2*a(n-4)
A164405 a(n)= +2*a(n-1) -a(n-3) +a(n-6)
A164406 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -2*a(n-4) -a(n-6)
A164407 a(n)= +a(n-1) +a(n-2) +a(n-4)
A164408 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-4)
A164409 a(n)= +2*a(n-1) -a(n-2) +a(n-3)
A164410 a(n)= +a(n-1) +2*a(n-3)
A164411 a(n)= +a(n-1) +a(n-2) +a(n-5)
A164412 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-4) -a(n-5)
A164413 a(n)= +a(n-1) +a(n-2)
A164414 a(n)= +a(n-1) +2*a(n-3)
A164415 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-4)
A164416 a(n)= +a(n-2) +2*a(n-3) +2*a(n-4) +a(n-5)
A164417 a(n)= +a(n-1) +a(n-2) +a(n-4) +a(n-5) -a(n-6) -a(n-7)
A164418 a(n)= +a(n-1) +a(n-3) +a(n-4) +a(n-5) +a(n-6) +a(n-7)
A164419 a(n)= +a(n-1) +a(n-2) -a(n-3) +a(n-4) +a(n-5) +a(n-6)
A164420 a(n)= +a(n-1) +a(n-2) -a(n-6)
A164421 a(n)= +a(n-1) +a(n-2) +a(n-5)
A164422 a(n)= +a(n-1) +a(n-3) +a(n-4) +a(n-5)
A164423 a(n)= +a(n-1) +a(n-2) +a(n-6) +a(n-7)
A164424 a(n)= +2*a(n-1) -a(n-2) +a(n-4) -a(n-6)
A164425 a(n)= +a(n-1) +a(n-3) +a(n-4) +a(n-5)
A164426 a(n)= +a(n-1) +2*a(n-3) -a(n-5) -a(n-6) -a(n-7)
A164427 a(n)= +a(n-1) +a(n-2) +a(n-4) -a(n-5)
<skip leap jump frog A-number range>
A164460 a(n)= +2*a(n-1) -a(n-3) -a(n-4) +a(n-5) +a(n-6) -a(n-7)
A164461 a(n)= +a(n-1) +a(n-2) +a(n-3) -2*a(n-4)
A164462 a(n)= +2*a(n-1) -a(n-2) +a(n-3) -a(n-5)
<skip A-number range>
A164480 a(n)= +2*a(n-1) -a(n-3)
A164481 a(n)= +2*a(n-1) -a(n-3) -a(n-4) +2*a(n-5) -a(n-6)
A164482 a(n)= +a(n-1) +a(n-2) -a(n-4)
A164483 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -3*a(n-4) +a(n-6)
A164484 a(n)= +2*a(n-1) -3*a(n-4) +2*a(n-5)
<skip A-number range>
A164490 a(n)= +2*a(n-1) -2*a(n-3) +2*a(n-4) -a(n-5)
A164491 a(n)= +a(n-1) +a(n-2) +a(n-5) +a(n-6)
A164492 a(n)= +2*a(n-1) -a(n-2) +a(n-4) +a(n-7)
A164493 a(n)= +2*a(n-1) -a(n-2) +a(n-3) -a(n-4) +a(n-5) +a(n-7)
A164494 a(n)= +2*a(n-1) -a(n-2) +a(n-3)

I presume the irregularities in the recurrences indicate how
far the substrings that are avoided have common overlapping substrings.

RJM