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 ?
0
$\begingroup$
$\endgroup$
1
$\begingroup$
$\endgroup$
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$.
answered May 24 '17 at 21:16
-
$\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
-
1
$\begingroup$
$\endgroup$
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.
-
-
-
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
