(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Find a recurrence relation for the number of bit strings of lengthnthat containthree 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 doesnothave k bit strings..

Thank you

master cherundo

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: [Recurrence Relation]three conscutive 0's in bit string

**Physics Forums | Science Articles, Homework Help, Discussion**