find a recurrence relation for the sequence

Question

Let $a_n$ be the number of words of length $n$ containing only letters “X” and “Y” without two consecutive “Y”. For example, $a_3 = 5$ since there are exactly five such words: $$\mathrm{XXX, XXY, XYX, YXX, YXY}$$

I know $a_1=2$ because it can be X or Y, and that $a_2=3$ because it can be XY or XX or YX.

But I do not know how to find a recurrence relation for the sequence $a_n$.

Answer 1

Think of building the words for $n+1$ by starting with the ones for $n$ and adding $X$ at the end of all of them, then adding $Y$. If no word at $n$ ended with $Y$ this procedure would imply that you could double the number of words each time. The problem is that this will not be the case, and to complete the procedure you will have to eliminate the words with $YY$ at the end. Let, $b_n$ be the number of words at step $n$ that end with $Y$. Then,

$$ a_{n+1} = 2a_n - b_n. \tag1$$

Now, notice that $a_2 = 3$ and $b_2=1$. That means that in the next step, the ones that you add an $X$ to the end will obviously not end in $Y$. The ones that you add $Y$ to the end only $a_2-b_2$ will survive the elimination. That means that $b_3=a_2-b_2$. Extrapolating this logic leads to

$$ b_{n+1} = a_n-b_n. \tag2$$

Putting equations $(1)$ and $(2)$ together leads to the desired system of recurrence relations, with initial conditions $a_1=2$ and $b_1=1$.

Or, solve for $b_n$ in $(1)$ which gives

$$ b_n = 2a_n - a_{n+1} $$

and plug this into $(2)$ to get

$$ 2a_{n+1} - a_{n+2} = a_n-2a_n + a_{n+1} , $$

which simplifying leads to

$$ a_{n+2} = a_{n+1}+a_n. $$

Answer 2

The strings of length $n+1$ come in two types: those ending in X, and those ending in Y.

The ones ending in X can have any of the $a_n$ valid strings of length $n$ beforehand. So, we have $a_n$ of those.

The ones ending in Y have to actually end in XY. Before that, any of the $a_{n-1}$ valid strings of length $n-1$ are fine.

So, $a_{n+1} = a_n + a_{n-1}$.

This gives you a familiar sequence.