Let $T(n)$ denote the number of but strings of length $n$ containing 5 consecutive 0's.
Total no. of bit strings of length $n = 2^n$
So, no. of bit strings of length $n$ not containing 5 consecutive 0's = $T(n)' = 2^n - T(n)$
Now, we can form a recurrence relation for $T_n$. We can for a bit string of length $n$ containing 5 consecutive 0's in two ways:
- from a bit string of length $n-1$, containing 5 consecutive 0's by adding either 0 or 1 at end.
- from a bit string of length $n-6$, not containing 5 consecutive 0's by adding 100000 at end.
These two covers any possible bit strings containing 5 consecutive 0's. In the second case we needed "100000" and not "00000" as "00000" would cause strings already considered in 1.
$T(0) = T(1) = T(2)= T(3) = T(4) = 0, T(5) = 1$
$T(n) = 2T(n-1) + T(n-6)' \\= 2T(n-1) + 2^{n-6} -T(n-6) $
We get,
$T(6) = 2T(5) + 2^0 - T(0) = 3$
$T(7) = 2T(6) + 2^1 - T(1) = 8 $
$T(8) = 2T(7) + 2^2 - T(2) = 20$
$T(9) = 2T(8) + 2^3 - T(3) = 48$
$T(10) = 2T(9) + 2^4 - T(4) = 112$
The number of bit strings having 5 consecutive 1's must also be 112.
Now, we need to find the number of bit strings of length 10 containing 00000 as well as 11111. There are only 2 possibilities:
1111100000 and
0000011111
Thus no. of bit strings of length 10, having either five consecutive 0's or 5 consecutive 1's = 112 + 112 - 2 = 222