Power Series of Recurrence Let n be a Natural number. Define $\ S_n $ to be the set of compositions of $\ n $ where no part is equal to 2, and let $\ a_n = |S_n| $.
It is trivial that:
$$
a_n = [x^n] \frac{1-x}{1-2x+x^2-x^3}
$$
The power series gives the recurrence $\ a_n - 2a_{n-1} - a_{n-3} = 0 $ for $\ n >= 3 $.
This is equivalent to:
$$
a_n + a_{n-2} = 2a_{n-1} + a_{n-3}
$$
Give a combinatorial proof of this recurrence using bijections.
Any hints?
 A: Let $b_n$ the number of compositions of $n$. Recall the proof that $b_n = 2 \ b_{n-1}$. We basically take the compositions of $n$, if $1$ occurs at the first position, then the remaining is a composition of $n-1$, and if a number $\ge 2$ occurs at the first position, then we subtract that number by $1$ to obtain a composition of $n-1$.
Now, we need to show that $a_n = 2 \ a_{n-1} - a_{n-2} + a_{n-3}$. So, we start with a $2$ avoiding composition of $n$. Call such compositions good. 


*

*If $1$ occurs at the first position, then discard that number to get a composition of $n-1$. This will generate all good compositions of $n-1$. So total $a_{n-1}$ compositions.

*If a number $\ge 4$ appears at the first position, then subtract $1$ from that number to get a composition of $n-1$. This will generate all good compositions of $n-1$ except those which start from $1$. So total $a_{n-1} - a_{n-2}$ compositions. (Since the number of good compositions of $n-1$ starting from $1$ is $a_{n-2}$)

*Finally, if $3$ appears at the first position, then discard that number to get a composition of $n-3$. This will generate all good compositions of $n-3$. So total $a_{n-3}$ compositions.


Thus, $a_n =  2 \ a_{n-1} - a_{n-2} + a_{n-3}$.
