Power Series of Recurrence

Question

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?

Answer 1

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.

1. 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.
2. 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}$)
3. 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}$.