- 14

- 0

**1. Homework Statement**

Find a recurrence relation for the number of bit strings of length

*n*

**that contain**three consecutive [tex]0[/tex]s.

**3. The Attempt at a Solution**

Divide the bit strings into two condition: one that have three consecutive [tex]0[/tex]s, another that does not. Let [tex]x_i[/tex] denote the bit strings of length n that fulfill that condition. Then, we can get [tex]x_i[/tex] by adding a 0 or a 1 to [tex]x_{i-1}[/tex]. But, there is another bit strings that included in [tex]x_i[/tex]. That is by adding [tex]1000[/tex] string to bit strings of length [tex]n-3[/tex] that does not have three consecutive 0s. This is can be write by [tex]2^{n-4}-x_{n-4}[/tex]. So, we get [tex]x_n=2x_{n-1}-x_{n-4}+2^{n-4}[/tex].

Is my recurrence relation right?

Examples i ever seen is just discuss about bit strings of length n that does

**not**have k bit strings..

Thank you

master cherundo

Last edited: