Find a recurrence relation for the number of binary strings of length “n” that do not contain three of the same number in a row.

How do I approach this problem?

Question

Find a recurrence relation for the number of binary strings of length “n” that do not contain three of the same number in a row.  

How do I approach this problem?

anonymous · Answer

I'd start off by creating the sequence that counts the number of strings that DO contain three of the same number in a row. Call this sequence $b_n$, then clearly $b_1,b_2=0$, while $b_3=2$ (since you can have $111$ or $000$).

Then whatever this sequence will be, let $a_n$ denote the number of strings that DO NOT contain the three-in-a-row pattern, so $a_n=2^n-b_n$.

All this to say you'd find a closed form for $a_n$, then make a recurrence relation out of that.

sh3lsh · Answer

I've got to close this question and ask an easier one so I understand the foundation of recurrence relationships. I'm totally confused.

sh3lsh · Answer

Could you continue to help me on this question?

anonymous · Answer

Actually, here's a more direct way of finding what you want.

Suppose $x$ is a binary string of length $n$. This string can end in $1$, $0$, $11$, or $00$. (We're basically considering the cases where the last two digits are distinct or the same consecutive digit.)

So letting $a_n$ be the total number of possible $n$-length binary strings without $111$ or $000$, we'll let $b_n$ denote the number of such strings that end in $1$, $c_n$ the number of such strings ending in $0$, $d_n$ for those ending in $11$, and $e_n$ for those ending in $00$.

In other words, we have the following relation:
$$a_n=b_n+c_n+d_n+e_n$$
What we want to do is write $b_n,c_n,d_n,e_n$ in terms of previous terms in the sequence $\{a_n\}$. Does that make sense so far?