Find a recurrence relation for the number of bit strings
of length n that do not contain three consecutive 0s.
I tried to solve this problem :
i) starts with 1 -> $a_{n-1}$
ii) starts with 000 -> $a_{n-3}$
iii) starts with 001 -> $a_{n-3}$
iv) starts with 01 -> $a_{n-2}$
so the total relation : $a_{n-1}+a_{n-2}+2a_{n-3}$
But in my book the result is : $a_{n-1}+a_{n-2}+a_{n-3}$
Where did i go wrong?
Best Answer
Let $s_n$ denote a string of length $n$ that does not have 3 consecutive zeros, and $a_n$ the number of such strings
Take a string of length $n-1$ that does not have 3 consecutive zeros, $s_{n-1}$ If we add a 1 to this string, then we get a string $s_n$.
Take a string $s_{n-2}$ If we add $10$ at the end, then we get a string $s_n$. Notably, we did not get any string we got in the previous step since all those strings ended in 1.
Take a string $s_{n-3}$ If we add $100$ at the end we get a string $s_n$. Notably we did not get any string we got in the previous 2 steps since they did not end with 00.
Now note that we actually got all possible strings $s_n$: all those that end in 1 (i.e. the last 3 digits could be 001, 011, 101 and 111), all those that end in 10 (i.e. the last 3 digits could be 010 and 110) and all those that end in 100. There are no other possibilities without having 3 consecutive zeros.
We thus find that $a_n=a_{n-1}+a_{n-2}+a_{n-3}$
The mistake you made was in your part ii) in which you counted the strings that start with 000, which is not allowed.