Compositions with no 2

We generate the compositions of $n$ without $2$ ’s recursively by the following process: to any such composition of $n -1$ , one can add a $1$ or increase the last summand by $1$ .

However, this process needs two corrections.

First, we must separately generate those compositions that end in $3$ , since they will not be generated by this recursive method. They come from adding a $3$ to compositions of $n-3$ .

Secondly, we must subtract the compositions of $n-1$ that initially ended in $1$ , since they would now end in $2$ under this process. The number of such compositions corresponds to compositions of length $n-2$ .

So, we have $C_n=2C_{n-1}-C_{n-2}+C_{n-3}$ .

Starting from $C_1=C_2=1;C_3=2$ , we get $C_{15}=\boxed{1897}$ .