What's wrong with this recursion of counting codes of length $n$ formed by $a$, $b$, and $c$ such that no three consecutive letters are distinct I found the following problem in a combinatorics book and gave it a try.

Let $B_n$ denote the set of codes of length $n$ formed by using the letters $a$, $b$, and $c$, none of which contains three consecutive letters that are distinct (so at least two of the three letters are the same). Express $|B_n|$ as a recursion.

Let $X_n$, $Y_n$, and $Z_n$ denote the sets of codes of length $n$ ending with $a$, $b$, and $c$ respectively. Then $|B_n| = |X_n| + |Y_n| + |Z_n|$.
A code of length $n$ ending with $a$ can be formed from a code of length $n - 2$ by the following three ways.


*

*Appending $aa$, $ba$, and $ca$ after a code ending with $a$.

*Appending $aa$ and $ba$ after a code ending with $b$.

*Appending $aa$ and $ca$ after a code ending with $c$.


Hence $|X_n| = 3 \cdot |X_{n - 2}| + 2 \cdot |Y_{n - 2}| + 2 \cdot |Z_{n - 2}|$. By symmetry, $|Y_n| = 2 \cdot |X_{n - 2}| + 3 \cdot |Y_{n - 2}| + 2 \cdot |Z_{n - 2}|$ and $|Z_n| = 2 \cdot |X_{n - 2}| + 2 \cdot |Y_{n - 2}| + 3 \cdot |Z_{n - 2}|$.
But, $|X_n| = |X_{n - 2}| + 2 \cdot (|X_{n - 2}| + |Y_{n - 2}| + |Z_{n - 2}|) = |X_{n - 2}| + 2 \cdot |B_{n - 2}|$. Again, by symmetry, $|Y_n| = |Y_{n - 2}| + 2 \cdot |B_{n - 2}|$ and $|Z_n| = |Z_{n - 2}| + 2 \cdot |B_{n - 2}|$.
Hence, $|B_n| = (|X_{n - 2}| + |Y_{n - 2}| + |Z_{n - 2}|) + 6 \cdot |B_{n - 2}| = 7 \cdot |B_{n - 2}|$ with $|B_1| = 3$ and $|B_2| = 9$. But the book's answer is $|B_{n}| = 2 \cdot |B_{n - 1}| + |B_{n - 2}|$. What did I get wrong?
 A: You have two cases to consider: strings that end in $x x$ and strings that end in $x y$ ($x \ne y$). Call the numbers of each of length $n$ respectively $u_n$ and $v_n$, set up recurrences for both. You are interested in $u_n + v_n$.


*

*$\ldots xx$: You can add a new $x$ (1 possibility) to get a new $\ldots xx$,
or anything else to get an $\ldots xy$ (2 options)

*$\ldots xy$: If you add an $x$, you get an $\ldots xy$ (1 option), if you add a $y$ you get a $\ldots xx$ (1 option)


This leads to the system of recurrences:
\begin{align}
u_{n + 1} &= u_n + v_n \\
v_{n + 1} &= 2 u_n + v_n
\end{align}
As starting points for $\ldots xx$ you have $u_2 = 3$, for $\ldots xy$ it is $v_2 = 6$, by "running the recurrences backwards" you get $u_0 = - 3$ and $v_0 = 6$. These values are pure fiction, the real starting points are $u_3 = 9$ and $v_3 = 12$.
Subtracting you get $v_{n + 1} - u_{n + 1} = u_n$,  so $v_{n + 1} = u_{n + 1} + u_n$; substituting in $u_{n + 2}$ gets you $u_{n + 2} = 2 u_{n + 1} + u_n$. But from the first recurrence the value you are really interested in, $u_n + v_n$, is nothing more than $u_{n + 1}$, which satisfies the same recurrence. Thus you have that
$$
\lvert B_{n + 2} \rvert = 2 \cdot \lvert B_{n + 1} \rvert + \lvert B_n \rvert
$$
as was requested.
Now use generating functions. Define $U(z) = \sum_{u \ge 0} u_n z^n$ and $V(z) = \sum_{u \ge 0} v_n z^n$, multiply the recurrences by $z^n$, sum each over $n \ge 0$, and express in terms of the generating functions:
\begin{align}
\frac{U(z) - u_0}{z} &= U(z) + V(z) \\
\frac{V(z) - v_0}{z} &= 2 U(z) + V(z)
\end{align}
This gives:
\begin{align}
U(z) &= - \frac{3 - 9 z}{1 - 2 z - z^2} \\
V(z) &= \frac{6 - 12 z}{1 - 2 z - z^2}
\end{align}
But you are interested in
$$
B(z) = U(z) + V(z) = 3 \frac{1 - z}{1 - 2 z - z^2}
$$
Next step is to expand as partial fractions, and read off the coefficients from the resulting terms. Sadly, the zeros of the denominator are $-1 \pm \sqrt{2}$, so this gets ugly. In the immortal words of all texbook writers, "the details are left as an exercise for the reader."
