0
$\begingroup$

Let $f(n)$ denote the number of bit strings. (Words from the alphabet $\{0,1\}$) of length $n$ which do not contain three consecutive zeros. How would you write a linear recurrence of order 3 with adequate initial conditions for $f(n)$. Also need to verify it gives the correct answer for $n = 6$. How would you approach this ?

$\endgroup$
1
$\begingroup$

Hint: Let $b(n)$ be the number of such strings whose last bit is $0$, and $c(n)$ the number whose last two bits are $0$. It's easy to write $f(n+1)$, $b(n+1)$ and $c(n+1)$ in terms of $f(n)$, $b(n)$ and $c(n)$. Then write everything in terms of $f$.

$\endgroup$
  • $\begingroup$ I just don't understand this part " f(n) denote the number of bit strings, words from the alphabet{0,1} $\endgroup$ – M.Jones May 24 '17 at 21:47
  • $\begingroup$ For example, in the case $n=3$ the allowed bit strings are $001$, $010$, $011$, $100$, $101$, $110$, $111$. $\endgroup$ – Robert Israel May 24 '17 at 22:25
  • $\begingroup$ Ahh that makes sense ! $\endgroup$ – M.Jones May 24 '17 at 22:28
1
$\begingroup$

see f(1) = 2, f(2) = 4 and f(3) = 7. from n$\geq$4 onwards, we have to think. Hmm..

f(n-1) might not have any zeros at the end of it, or one zero at the end, or two zeros at the end. Depending on that we can do certain things to each of them and that should give you a recurrence relation.

For example, if f(n-1) has no zeros at the end then we can either append a 0 or 1 at the end and get two times the string given by the f(n-1).

for other two, you can do adjustments accordingly and reach a recurrence involving three terms.

$\endgroup$
  • $\begingroup$ how does f(3) = 7 ? $\endgroup$ – M.Jones May 24 '17 at 21:32
  • $\begingroup$ or is that just an assumption $\endgroup$ – M.Jones May 24 '17 at 21:33
  • 1
    $\begingroup$ when we try to make a string out of {0,1} of length three, we have three choices for each spot but want to rule of 000, hence 2*2*2-1 = 7 $\endgroup$ – HumbleStudent May 24 '17 at 22:17

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.