<s>[INST] Words of length $10$ in alphabet $\{a,b,c\}$ such that the letter $a$ is always doubled 
Compute the number of words of length $10$ in alphabet $\{a,b,c\}$ such that letter $a$ is always doubled (for example "$aabcbcbcaa$" is allowed but "$abcbcaabcc$" is forbidden).

I am looking for a quick/efficient way to resolve this problem. I thought of fixing "$aa$" in the beginning then draw a tree of the next possibilities but this tree will end up to be a whole forest. Can you help me ?
 [/INST] A word of length $n$ is either a word of length $n - 1$ and a $b$ or a $c$, or a word of length $n - 2$ and $aa$. Call the number of words of length $n$ $x_n$, you see $x_0 = 1$, $x_1 = 2$, and:
$\begin{align*}
   x_{n + 2}
     &= 2 x_n + x_{n - 2}
\end{align*}$
Solving this using generating functions is routine. Define:
$\begin{align*}
    g(z)
      &= \sum_{n \ge 0} z_n z^n
\end{align*}$
Multiply your recurrence by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:
$\begin{align*}
   \sum_{n \ge 0} x_{n + 2} z^n
     &= 2 \sum_{n \ge 0} x_{n + 1} z^n + \sum_{n \ge 0} x_n z^n \\
   \frac{g(z) - x_0 - x_1 z}{z^2}
     &= 2 \frac{g(z) - x_0}{z} + g(z)
\end{align*}$
Solve for $g(z)$ using the initial values, express as partial fractions:
$\begin{align*}
   g(z)
     &= \frac{1}{1 - 2 z - z^2} \\
     &= \frac{1}{(1 - (1 - \sqrt{2}) z) (1 - (1 + \sqrt{z}) z)} \\
     &= \frac{\sqrt{2} - 1}{2^{3/2} (1 + (\sqrt{2} - 1) z)}
          + \frac{\sqrt{2} + 1}{2^{3/2} (1 - (\sqrt{2} + 1) z)}
\end{align*}$
We need the coefficient of $z^n$, as this is just geometric series:
$\begin{align*}
  [z^n] g(z)
    &= (-1)^n \frac{\sqrt{2} - 1}{2^{3/2}} (\sqrt{2} - 1)^n
         + \frac{\sqrt{2} + 1}{2^{3/2}} (\sqrt{2} + 1)^n
\end{align*}$
Noting that $\rvert \sqrt{2} - 1 \lvert < 1$, and furthermore the respective coefficient is also less than $1$, you have finally that:
$\begin{align*}
   x_n
     &= \operatorname{round}
          \left( \frac{\sqrt{2} + 1}{2^{3/2}} (\sqrt{2} + 1)^n \right)
\end{align*}$
(No, this isn't the best way to compute $x_n$ for large $n$, but it shows how the value grows).
</s>