Question: Let $\mathcal{J}_{n}$ denote the set of binary strings with no three consecutive $1$s. Let $j_n$ = |$\mathcal{J}_{n}$|. Determine $\mathcal{J}_{1}$, $\mathcal{J}_{2}$, and $\mathcal{J}_{3}$ and then find a recurrence for $j_n$.
Solution: We find $\mathcal{J}_1=\{0,1\}, \mathcal{J}_2=\{00,01,10,11\}$ and $\mathcal{J}_3=\{000,001,010,011,100,101,110\}$. Assume now that $n\geq3$. If $S$ is a string in $\mathcal{J}_n$ then has one of the following three forms
- An initial substring of $0$ followed by a string in $\mathcal{J}_{n-1}$
- An initial substring of $10$ followed by a string in $\mathcal{J}_{n-2}$
- An initial substring of $110$ followed by a string in $\mathcal{J}_{n-3}$
It follows that for $n\geq3$ we have $j_n=j_{n-1}+j_{n-2}+j_{n-3}.$
What's the logic behind the answer? Why does it only include initial substring for $0$, $10$, and $110$? What about $11$, $00$....?
Is there a strategy for solving this kind of recurrence problem? How do we define the initial condition?
The logic is: you know it cannot start with 111, at least one of the first three characters must be zero.
If the first zero is the first character, then the remaining characters must be a sequence in $J_{n-1}$
If the first zero is the second character, then the remaining characters must be a sequence in $J_{n-2}$
If the first zero is the third character, then the remaining characters must be a sequence in $J_{n-3}$
That exhausts all possibilities.
The recurrence relation is the sum of those three possibilities, since they’re mutually exclusive and exhaustive.
The initial condition is to count the sizes of $J_1, J_2,$ and $J_3$.