Am I on the right path solving this problem from 11 n-bits?

24 Views Asked by At

So the problem is to find how many 11-bit strings will have no consecutive three zeroes.

I have used recurrence to solve this problem. I set $T(n)$ to be the number of strings of size n that there will be no consecutive three zeroes. If the firsst digit is filled with 1, then you get $T(n-1)$ that can be filled and then you get $T(n-2) and T(n-3)$ for the second and third boxes.

T1- 2 (can be either 0 or 1) T2 - 4 (00,01,10,100) T3 - 7 (991,010,011,100,101,110, 111)

Now is when I start adding up the previous three terms up T4 = T1+T2+T3 = 13

T5 = T2+T3+T4 = 24

I keep doing this unitl I get to T11

T11 - T10 + T9+ t8 = 927 11 bit strings with no consecutive three 0s in a row