How many bit strings of length n are there with two or more consecutive zeros?

Question

$a_n = 2^n - (a_{n-2} + a_{n-1})$

I have read this formula somewhere but don't know how its used here $a_n$ is the number of bit-strings of length $n$

Answer 1

The formula I get is this:

$$a_n=2^{n-2}+a_{n-1}+a_{n-2}$$

Reasoning:

Consider all such strings of length $n\geq2$:

If the first entry of such string is $1$, then the first entry doesn't contribute with anything to the property "have at least $2$ consecutive $0$'s" since and thus we can pretend it doesn't exist. Hence the number of such strings that start with $1$ is $a_{n-1}$.

If a string starts with $01$, then again, we need $2$ consecutive $0$'s and the $01$ has no contribution, so we could just erase the first $2$ entries and get that the number of such sequences is $a_{n-2}$

Finally, if it starts with $00$, then it doesn't matter what the other $n-2$ entries are, since we already have the $2$ consecutive $0$'s.

Since these are all possible cases we are done.

https://www.wolframalpha.com/input/?i=f(n)%3D2%5E(n-2)%2Bf(n-1)%2Bf(n-2),+f(1)%3D0,+f(2)%3D1

This gives a general formula which looks quite ugly to me.

Hopefully this helps