Combinatoric meaning of $a_n=5a_{n-1} - 6a_{n-2}$ 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}
$$
?

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 


*

*$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  

*$a_{n-1}=3 a_{n-2} + b_{n-2}$ in exactly the same way

*$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)

