A340215 Consider constructing binary words that begin with 0 such that the subword 00, whenever it appears, is followed by 111. Then a(n) counts such words at length n (including those where the string 111 is yet being completed - see Example).

1, 2, 3, 5, 8, 14, 24, 41, 70, 119, 203, 346, 590, 1006, 1715, 2924, 4985, 8499, 14490, 24704, 42118, 71807, 122424, 208721, 355849, 606688, 1034344, 1763456, 3006521, 5125826, 8739035, 14899205, 25401696, 43307422, 73834944, 125881401, 214615550, 365898647, 623821619, 1063555210, 1813258230

Offset

1,2

Comments

a(n) follows the Fibonacci recursion with an additional term (see Formula).

Links

Table of n, a(n) for n=1..41.

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

Formula

a(n) = a(n-1) + a(n-2) + a(n-5) with a(1) = 1, a(2) = 2, a(3) = 3, a(4) = 5, a(5) = 8.

G.f.: x*(1 + x)/(1 - x - x^2 - x^5). - Stefano Spezia, Jan 01 2021

Example

a(5)=8: 00111, 01001, 01010, 01011, 01100, 01101, 01110, 01111. Note 01001 gets counted at n=5, 010011 at n=6, and 0100111 at n=7.

Crossrefs

Sequence in context: A316474 A086661 A018154 * A114831 A343161 A274110

Adjacent sequences: A340212 A340213 A340214 * A340216 A340217 A340218

Keyword

nonn,easy

Author

Enrique Navarrete, Dec 31 2020

Status

approved