How many consecutive ‘111’ in binary

It is definitely trivial if binary is less than 3 bits long, there are no consecutive ‘111‘s there.

But what if binary is three bits, or longer – how to approach this question?

Well, we can start from very beginning. Lets observe:
0 bits – 0 possibilities
1 bit – 0 possibilities
2 bits – 0 possibilities

3 bits – 1 possibility, out of 8 possible.

We can add any one bit (lets agree we add bits from right for convenience), so all combinations looking like 111x are fine, lets build function.

We can also add 1 to combinations ending in ‘o11’, but we shouldnt count sequences with ‘xx111xx’ somewhere inside, since those are already taken into count.

So – with initial values ,,,, and sequence itself goes:1, 3, 8, 20, 47, 107, 238, 520, 1121,…

Sagemath simulation online