Combinatoric meaning of $a_n=5a_{n-1} - 6a_{n-2}$

Question

I've solved the following recurrence relation: $a_n=5a_{n-1} - 6a_{n-2}$ using generating functions, to be: $a_n=3^n-2^n$. It is possible to give a meaning to $3^n-2^n$, and that is:

Consider the following set: $S=\{a,b,c\}$.

$3^n$ is the number of sequences of length n with repetition using all letters from the set $S$.

$2^n$ is the number of sequences of length $n$ with repetition using two of the three letters of the set $S$.

So $3^n - 2^n$ we can say that it is counting all sequences of length $n$ from the set $S$ with at least one $a$.

My question now is, how to give a combinatorial interpretation, that agrees to the one I gave, to that recurrence relation: $$ a_n=5a_{n-1} - 6a_{n-2} $$ ?

Answer 1

Let $a_n$ be the number of sequences of length $n$ from the set $S$ with at least one $a$

Let $b_n$ be the number of sequences of length $n$ from the set $S$ with no $a$

Then using the combinatorial analogy we can easily say

1. $a_n=3 a_{n-1} + b_{n-1}$ since we can append any of the three to a satisfactory sequence but only $a$ to an unsatisfactory one
2. $a_{n-1}=3 a_{n-2} + b_{n-2}$ in exactly the same way
3. $b_{n-1}=2 b_{n-2}$ since we only have two choices for extending an unsatisfactory sequence

and we can combine these to eliminate $b_{n-1}$ and $b_{n-2}$ with

• $ b_{n-2}=a_{n-1}-3 a_{n-2}$ by reordering (2)
• $ b_{n-1}=2a_{n-1}-6 a_{n-2}$ by substituting into (3)
• $a_n=5 a_{n-1} -6 a_{n-2}$ by substituting into (1)