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 ?
 A: Say there are $i$ occurrence of 'aa' that you "tape" together.  The you have a total of $10-i$ slots, of which $i$ has to be 'aa' and the other $10-2i$ are either 'b' or 'c'.  That gives the total
$$
\sum_{i=0}^5\sum_{j=0}^{10-2i}\binom{10-i}i \binom{10-2i}j.
$$
A: Here is a second approach: Let $x_n$ $(n\geq0)$ denote the number of admissible words having $n$ letters. Then
$$x_0=1,\quad x_1=2,\qquad x_n=2x_{n-1}+x_{n-2}\quad (n\geq2)\ .$$
The characteristic equation of the recursion is $\lambda^2-2\lambda-1=0$ with roots $\lambda=1\pm\sqrt{2}$. It follows that
$$x_n=c(1+\sqrt{2})^n+c'(1-\sqrt{2})^n\qquad(n\geq0)\ ,$$
where the constants $c$, $c'$ have to be determined from the initial conditions. The computation gives
$$c={2+\sqrt{2}\over4},\qquad c'={2-\sqrt{2}\over4}\ .$$
Now $\bigl|c'(1-\sqrt{2})^n\bigr|<{1\over2}$ for all $n\geq0$. We therefore can write
$$x_n={\tt round}\left({2+\sqrt{2}\over4}(1+\sqrt{2})^n\right)\qquad(n\geq0)\ .$$
This gives
$$x_{10}={\tt round}\bigl(5740.9999782267896753\bigr)=5741\ .$$
This coincides with the value obtained by ${\tt user10354138}$.
A: You can break this up into cases based on how many aa pairs there are, which can range from $0$ to $5$. Consider, for example, the case that you have $3$ aa pairs. Then you have four other letters that are all either b or c, so there are $2^4$ ways to choose the subsequence formed by those letters. Then thinking of each aa pair as a single letter, you have $7$ letters, and you need to choose $3$ of them to be an aa pair. This gives $2^4{7\choose 3}$ words with $3$ aa pairs.
In general, the number of words of this form with $i$ aa pairs is $2^{10-2i}{10-i\choose i}$. Then add up all terms of this form as $i$ goes from $0$ to $5$.
A: 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).
