Find and prove a recurrence relation that $t_n$ satisfies.

Question

Let $t_n$ be the number of lists of length $n$ with entries $a,b,c$ in which no two $a$'s occur consecutively and no two $b$'s occur consecutively. (There are no restrictions on $c$.) Find and prove a recurrence relation that $t_n$ satisfies.

The recurrence relation I've found is $t_{n+2}=2t_{n+1}+t_{n}$, for $n\geq2$ using examples but I'm not sure that I'm right!

Answer 1

Hint: let $u_n$, $v_n$ and $w_n$ be the number of such sequences that end in $a, b, c$ respectively. Find a system of recurrences for these.

Answer 2

Sequences of length $n+2$ fall into two classes: those that end with $cc$, and those that do not.

1. The number of sequences in the first class is $t_n$, since deleting the $cc$ at the end leaves a valid sequence of length $n$.

2. The number of sequences, $S$, in the second class is $2t_{n+1}$. There are $t_{n+1}$ ways to choose the first $n+1$ characters of $S$. Call this string of $n+1$ letters $T$.

   • If $T$ ends in an $a$, there are two ways to choose the last letter, $b$ or $c$.

   • If $T$ ends in a $b$, there are two ways to choose the last letter, $a$ or $c$.

   • If $T$ ends in a $c$, there are two ways to choose the last letter, $a$ or $b$. [Here, we use the fact that we are not counting strings ending in $cc$, as those were counted in $(1)$.]

The recurrence follows.