# Find a recurrence relation for the number of bit strings of length n that do not contain three consecutive 0s.

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?

• A string that does not contain three consecutive 0s cannot start with 000 as in your case (ii). – Fabio Somenzi Feb 4 '17 at 20:41
• oh, i missed it...thanks a lot – IAmBlake Feb 4 '17 at 20:49

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.