
95.2. Messages are coded using sequences consisting of zeroes and ones only. Only sequences with at most two consecutive ones or zeroes are allowed. (For instance the sequence 011001 is allowed, but 011101 is not.) Determine the number of sequences consisting of exactly 12 numbers.


Solution 1. Let $S_{n}$ be the set of acceptable sequences consisting of $2 n$ digits. We partition $S_{n}$ in subsets $A_{n}, B_{n}, C_{n}$, and $D_{n}$, on the basis of the two last digits of the sequence. Sequences ending in 00 are in $A_{n}$, those ending in 01 are in $B_{n}$, those ending in 10 are in $C_{n}$, and those ending in 11 are in $D_{n}$. Denote by $x_{n}, a_{n}, b_{n}, c_{n}$, and $d_{n}$ the number of elements in $S_{n}, A_{n}, B_{n}, C_{n}$, and $D_{n}$. We compute $x_{6}$. Because $S_{1}=\{00,01,10,11\}$, $x_{1}=4$ and $a_{1}=b_{1}=c_{1}=d_{1}=1$. Every element of $A_{n+1}$ can be obtained in a unique manner from an element of $B_{n}$ or $D_{n}$ by adjoining 00 to the end. So $a_{n+1}=b_{n}+d_{n}$. The elements of $B_{n+1}$ are similarly obtained from elements of $B_{n}, C_{n}$, and $D_{n}$ by adjoining 01 to the end. So $b_{n+1}=b_{n}+c_{n}+d_{n}$. In a similar manner we obtain the recursion formulas $c_{n+1}=a_{n}+b_{n}+c_{n}$ and $d_{n+1}=a_{n}+c_{n}$. So $a_{n+1}+d_{n+1}=\left(b_{n}+d_{n}\right)+\left(a_{n}+c_{n}\right)=x_{n}$ and $x_{n+1}=2 a_{n}+3 b_{n}+3 c_{n}+2 d_{n}=3 x_{n}-\left(a_{n}+b_{n}\right)=3 x_{n}-x_{n-1}$. Starting from the initial values $a_{1}=b_{1}=c_{1}=d_{1}=1$, we obtain $a_{2}=d_{2}=2, b_{2}=c_{2}=3$, and $x_{2}=10$. So $x_{3}=3 x_{2}-x_{1}=3 \cdot 10-4=26, x_{4}=3 \cdot 26-10=68, x_{5}=3 \cdot 68-26=178$, and $x_{6}=3 \cdot 178-68=466$.
