How to calculate no. of binary strings containg substring “00”? [duplicate]

Solution 1:

Let $a_n$ be the number of strings of length $n$ that do contain $00$, and let $b_n$ be the number that don't; of course $b_n=2^n-a_n$, but it's actually easier to determine $b_n$. Consider a string of length $n$ that does not contain $00$. If it ends in $1$, it can be obtained from a string of length $n-1$ that does not contain $00$ by appending a $1$. If it ends in $0$, it can be obtained from a string of length $n-2$ that does not contain $00$ by appending $10$. Assuming that $n\ge 2$, every string of length $n$ that does not contain $00$ is obtained in exactly one of these two ways, so $b_n=b_{n-1}+b_{n-2}$. Clearly $b_0=1$, since the empty string does not contain $00$, and $b_1=2$. The recurrence is the same as that for the Fibonacci numbers, $b_0=F_2$, and $b_1=F_3$, so in general we have $b_n=F_{n+2}$ and therefore

$$a_n=2^n-F_{n+2}\;.$$

Using the closed-form expressions in the linked article, we can write

$$a_n=2^n-F_{n+2}=2^n-\frac1{\sqrt5}\left(\varphi^{n+2}-\widehat\varphi^{n+2}\right)=2^n-\left\lfloor\frac{\varphi^{n+2}}{\sqrt5}+\frac12\right\rfloor\;,$$

where $\varphi=\frac12\left(1+\sqrt5\right)$ and $\widehat\varphi=\frac12\left(1-\sqrt5\right)$.