question in discrete mathematics

Question

I have questions. Can anyone help me to get the idea or figure out this problem. Find a recurrence relation. If an denote the number of words from the alphabet W={A,B,C} of length n with no two adjacent letters being A'S. thank you very much

Answer 1

Call a string with no two consecutive A's good. Let $x_n$ be the number of good strings of length $n$ that end in $A$, and let $y_n$ be the number of good strings of length $n$ that don't end in A.

Note that $x_{n+1}=y_n$, since we get the good strings of length $n+1$ that end in A by appending an A to a good (possibly empty) string of length $n$ that doesn't end in A.

Note also that $y_{n+1}=2(x_n+y_n)$. This is because we get all the good strings of length $n+1$ that don't end in A by appending a B or C to any good string of length $n$.

From the preceding recurrence, we get $$y_{n+2}=2x_{n+1}+2y_{n+1}=2y_n+2y_{n+1}.\tag{$1$}$$ Also, $$x_{n+2}=y_{n+1}=2x_n+2y_n=2x_n+2x_{n+1}.\tag{$2$}$$

If $g_n$ is the number of good strings of length $n$, then $g_n=x_n+y_n$.

We conclude from $(1)$ and $(2)$ that $g_{n+2}=2g_n+2g_{n+1}$.

Remark: The method generalizes with no trouble to situations where we have A and $n$ other letters. If $n=1$, we get the Fibonacci recurrence.