Proving the number of $n$ length binary strings with no consecutive $1's$ $b_n$ is equal to $b_{n-1} + b_{n-2}$

Note that we could start with the base case $i = 0$. The empty bit string does not contain two consecutive $1$s, so $b_0 = 1$.

The reason that $b_1 = 2$ is that both bit strings of length $1$, $0$ and $1$, do not contain two consecutive $1$s. Similarly, $b_2 = 3$ because the three bit strings $00$, $01$, and $10$ satisfy the requirement that the bit string does not have two consecutive $1$s, while the only other bit string of length $2$, $11$, does violate the condition.

Let $n \geq 2$.

Any bit string of length $n - 1$ that does not contain two consecutive $1$s can be extended to a bit string of length $n$ that does not contain two consecutive $1$s by appending a $0$. Moreover, any permissible string of length $n$ that ends in $0$ can be reduced to a permissible bit string of length $n - 1$ by removing the final $0$. Hence, the number of permissible bit strings of length $n$ that end in $0$ is $b_{n - 1}$.

Any bit string of length $n - 2$ that does not contain two consecutive $1$s can be extended to a bit string of length $n$ that does not contain two consecutive $1$s by appending the string $01$. Moreover, any permissible bit string of length $n \geq 2$ that ends in $1$ must have a $0$ in the $(n + 1)$st position. Therefore, any permissible bit string of length $n$ that ends in $1$ can be reduced to a permissible bit string of length $n - 2$ by removing the $01$ in its last two positions. Hence, the number of permissible bit strings of length $n$ that end in $1$ is $b_{n - 2}$.

Since every permissible bit string ends in $0$ or $1$, we may conclude that the number of permissible bit strings is given by the recurrence relation \begin{align*} b_0 & = 1\\ b_1 & = 2\\ b_n & = b_{n - 1} + b_{n - 2},~\text{if}~n \geq 2 \end{align*}

You will notice that I argued that a permissible bit string of length $n - 1$ could be extended to a permissible bit string of length $n$ that ends in $0$, which shows that the number of bit strings of length $n$ that end in $0$ is at least $b_{n - 1}$. By showing that any permissible bit string of length $n$ that ends in $0$ can be reduced to a permissible bit string of length $n$, I also showed that the number of bit strings of length $n$ that end in $0$ is at most $b_{n - 1}$. Therefore, the number of such bit strings of length $n$ that end in $0$ is equal to $b_{n - 1}$.

Likewise, I demonstrated that any permissible bit string of length $n - 2$ could be extended to a bit string of length $n$ that ends in $1$ by appending the string $01$ and that any permissible bit string of length $n$ that ends in $1$ can be reduced to a permissible bit string of length $n - 2$ by removing the final $01$ to show that the number of permissible bit strings of length $n$ that end in $1$ is $b_{n - 2}$.

Rather than using induction, I used bijections to create the recurrence relation.