I have a question about this question:
Recurrence relation find the number of binary strings that contain two consecutive zeros
In your answer,
No, it takes each bit separately, except for the last two. It says the
string can end in 00,01,10,11. If it ends in 00 it is acceptable
regardless of what came before-that is the 2n−2. If it ends in
anything else, it must have been acceptable before, or have the 00
come from the addition. Adding a 1 can never make a string acceptable,
so you can add it to the end of an−1 strings. We still haven't
accounted for the ones that end in 10, and that is the an−2.
I'm a little confused about why the case '11' is counted in the a(n-1) case but not the a(n-2) case. Can you not also add '11' to the end of any a(n-2) string and maintain that the string before still has substring '00'?
Thanks in advance,
Eric
Best Answer
We can account for $11$ in the $a_{n-2}$, case but it makes the $a_{n-1}$ case harder to deal with. Here's what would happen:
We have $4$ endings we can add to an $n-2$ length string to get to an $n$ length string: $00,01,10$, and $11$. Of these, the $10$ case and the $11$ case can't add any consecutive $0$s, so together they give us $2a_{n-2}$ valid strings. As in the other construction the $00$ case gives us a $2^{n-2}$ term (since it doesn't matter what the previous digits were). Finally, we are left with the $01$ case. This case is a little tricky to deal with because it will not just give us $a_{n-1}$ strings because we have the additional restriction that the last digit of the $n-1$ length string is a $0$. Okay, so how many valid strings of length $n-1$ are there whose last digit is $0$?. Well, as we had before the number of valid length $n-1$ stings whose last digit is $1$ is just $a_{n-2}$. Hence the number of valid $n-1$ length string who end in $0$ is $a_{n-1}-a_{n-2}$. This gives us the recurrence relation $$a_n=2a_{n-2}+a_{n-1}-a_{n-2}+2^{n-2}=a_{n-2}+a_{n-1}+2^{n-2}$$ which is exactly what we had before except it took a bit more work.
The idea in the original solution is to avoid this difficulty by working backwards. First, if we add a $1$ to a valid $n-1$ length string, we get a valid $n$ length string, so we get an $a_{n-1}$ term (note here we are dealing with both the $01$ and $11$ cases because we are just requiring that the last digit be $1$). This leaves us with the $10$ and $00$ cases. The $00$ case we immediately deal with as before (getting a $2^{n-2}$ term). The $10$ case now just gives us a term of $a_{n-2}$ since we can't add any consecutive $0$s by adding $10$. Putting this into a recurrence relation gives us exactly the same thing as above, but we avoid having to cancel any terms.