Recurrence relation for 10 bit string

Question

Consider a bit-string of length 10. The number of string contain 3 consecutive 0’s or 3 consecutive 1’s are ________

How to generate recurrence relation for such questions?

Answer 1

Looking for a recursive method, I think that the best way is to setup a Markov chain.

Let's indicate with
$n$ the strings that do not contain three consecutive $0$'s nor three consecutive$1$'s; $y$ the strings that contain at least one triple of $0$'s or $1$'s.

Among the strings $n$, let's distinguish those which end in $00,\, 10,\, 01,\, 11$.

Then the transition matrix is clearly $$ \begin{array}{c|ccccc} {} & {n_{00} } & {n_{10} } & {n_{01} } & {n_{11} } & y \\ \hline {n_{00} } & 0 & 0 & {1/2} & 0 & {1/2} \\ {n_{10} } & {1/2} & 0 & {1/2} & 0 & 0 \\ {n_{01} } & 0 & {1/2} & 0 & {1/2} & 0 \\ {n_{11} } & 0 & {1/2} & 0 & 0 & {1/2} \\ y & 0 & 0 & 0 & 0 & 1 \\ \end{array} $$ with an initial vector which is $(1/4,\, 1/4,\,1/4,\,1/4,\, 0)$.

The matrix is diagonalizable in the complex field, if you need to algebraically compute its powers.

Answer 2

Hint: It may be easier to count the strings which do not contain three consecutive zeroes or three consecutive ones. Since there are $2^{10}$ possible bit strings of length $10$, a simple subtraction will then yield the number which do contain three consecutive zeroes or three consecutive ones.

To that end, let's say a bit string is acceptable if it does not contain three consecutive zeroes or three consecutive ones. Given an acceptable string, either its final two bits are equal or they are not, i.e. the string looks like ....XX or ....X. Try letting $a_n$ be the number of acceptable bit strings of length $n$ of the first type, and $b_n$ be the number of bit strings of length $n$ of the second type. If you can find a recursion for $a_n$ and $b_n$ in terms of $a_{n-1}$ and $b_{n-1}$ with suitable boundary conditions, then $a_n+b_n$ will be the total number of acceptable bit strings of length $n$.