Generating function for amount of words, only using letters A,B and C, without two or more successive A's.

Question

Question in the title; I kinda feel helpless about that one.

Answer 1

We will find a linear recurrence relation for the number of words. Finding a generating function for such relations are straightforward. Let $a_n$ be the number of words with length $n$. For $n>=2,$ consider words of length $n$. If the last letter is A, then the second last letter must be B or C, and the first $n-2$ letters can be any word that satisfies the condition. So there are $2a_{n-2}$ such words. If the last letter is B or C, then the first $n-1$ letters can be any word that satisfies the condition. So there are $2a_{n-1}$ such words. Thus our recurrence relation is $$a_n = 2a_{n-1} + 2a_{n-2}.$$ We also have $a_0=1$ (the empty word) and $a_1=3$. We finally find the generating function. If $f(x)$ is the generating function, then we have $$2xf(x) + 2x^2f(x) = f(x)-x-1$$ since the coefficient for $x^n$ on the LHS is $a_n = 2a_{n-1} + 2a_{n-2}$ except for the coefficients of 1 and x, which both fall one short. So the generating function is $$f(x) = \frac{x+1}{1-2x-2x^2}.$$