0
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.