For this problem, I used a proof by induction. My base case was essentially defining $b_1 = 2$, $b_2 = 3$, and then proceeding to the inductive step.
In the inductive step, I use strong induction. I assume the claim holds for $n=1,2,…i-1$ and show it holds for $i$.
We have by the inductive hypothesis $b_{i-1}$ is the number of $i-1$ length binary strings with no consecutive $1's$. To each of these such strings, we can add $0$ to generate $i$ length binary strings with no consecutive $1's$. We now have $b_{i-1}$ binary strings that end with $0$ and have no consecutive $1's$.
We have by the inductive hypothesis $b_{i-2}$ is the number of $i-2$ length binary strings with no consecutive $1's$. To each of these such strings, we can add $01$. These new strings are distinct from the strings we created above, as these strings end with a $1$, but the above strings end with a $0$. So, we have $b_{i-2}$ binary strings that end with $1$ and have no consecutive $1's$.
We note a binary string $B$ can be classified as such:
Ends with a 0: Last two digits are 10, 00. Case 1 considers all these strings
Ends with a 1: Last two digits are 01, 11. Case 2 considers all strings of the former case. The latter case is a violation, and each case ignores it.
Thus, $b_i = b_{i-1} + b_{i-2}$.
My problem here is:
1) Is my argument classifying the strings and then showing we counted correctly sufficient?
2) Is the proof by induction correctly formatted? I notice I am not using the fact $b_{i-1} = b_{i-2} + b_{i-3}$, but I do not know how to derive the conclusion without working on the assumption that $b_{i-1},b_{i-2}$ are indeed the correct number of binary strings without consecutive $1's$. It seems I am using induction right now to work under the assumption that the claim holds for all values $<i$, but could I not use induction and still work under this same assumption?
Best Answer
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.