How many sequences of ten binary digits are there in which neither two zeroes nor three ones ever appear in a row?
Solution
Let be the number of binary sequences of length satisfying the conditions and ending in 0 , let be the number ending in 01 , and let be the number ending in 11 . From the legal sequences of length , we find that . We now establish a recursion by building sequences of length from sequences of length . We can add a 0 to a sequence of length if and only if it ended with a 1 , so . We can have a sequence of length ending with 01 only by adding a 1 to a sequence of length ending in 0 , so . We can have a sequence of length ending with 11 only by adding a 1 to a sequence of length ending in 01 , so . We can now run the recursion: \begin{tabular}{c|c|c|c} & & & \\ \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{tabular} Our answer is then .