HMMT November

Let $a_{n}$ be the number of binary sequences of length $n$ satisfying the conditions and ending in 0 , let $b_{n}$ be the number ending in 01 , and let $c_{n}$ be the number ending in 11 . From the legal sequences of length $201,11,10$, we find that $a_{2}=b_{2}=c_{2}=1$. We now establish a recursion by building sequences of length $n+1$ from sequences of length $n$. We can add a 0 to a sequence of length $n$ if and only if it ended with a 1 , so $a_{n+1}=b_{n}+c_{n}$. We can have a sequence of length $n+1$ ending with 01 only by adding a 1 to a sequence of length $n$ ending in 0 , so $b_{n+1}=a_{n}$. We can have a sequence of length $n+1$ ending with 11 only by adding a 1 to a sequence of length $n$ ending in 01 , so $c_{n+1}=b_{n}$. We can now run the recursion: $$\begin{array}{c|c|c|c} n & a_{n} & b_{n} & c_{n} \\ \hline 2 & 1 & 1 & 1 \\ \hline 3 & 2 & 1 & 1 \\ \hline 4 & 2 & 2 & 1 \\ \hline 5 & 3 & 2 & 2 \\ \hline 6 & 4 & 3 & 2 \\ \hline 7 & 5 & 4 & 3 \\ \hline 8 & 7 & 5 & 4 \\ \hline 9 & 9 & 7 & 5 \\ \hline 10 & 12 & 9 & 7 \end{array}$$ Our answer is then $12+9+7=28$.