compositions and recurrence relation Let $b_n$ be the number of compositions of $n$ into parts that are larger
than $2$. Find a recurrence relation satisﬁed by $b_n$
 A: One (very inelegant) way to solve the problem is to calculate the first few values of $b_n$ and look up the sequence in the On-Line Encyclopedia of Integer Sequences. I get
$$\begin{array}{rcc}
n:&3&4&5&6&7&8&9&10&11&12\\
b_n:&1&1&1&2&3&4&6&9&13&19
\end{array}$$
OEIS returns eight hits, of which the second, A078012, turns out to be exactly what’s wanted. The entry gives the recurrence $b_n=b_{n-1}+b_{n-3}$ for $n\ge 4$, if we set $b_1=b_2=0$. Now that we have the answer, we can try to justify it.
Let $C_n$ be the set of compositions of $n$ with each part greater than $2$. We can split $C_n$ into $C_n'$, the set of compositions beginning with $3$, and $C_n''=C_n\setminus C_n'$. Clearly $|C_n'|=b_{n-3}$, so all that remains is to find a bijection between $C_n''$ and $C_{n-1}$. There’s a very simple one involving the first part of the composition; I’ll give you a chance to find it on your own.
A: For any $n\ge 3$, we have the trivial composition into $1$ part. In addition, there are the compositions with final entry $3$, and the ones with final entry  $4$, and the ones with final entry $5$, and so on up to the compositions that have final entry $n-3$. It follows that
$$b_n=b_{n-3}+b_{n-4}+b_{n-5}+\cdots +b_3 +1.\tag{$1$}$$
This is a recurrence, but not really what we are looking for. It would be nice to have a fixed length recurrence. 
Bumping the indices in $(1)$ up by $1$, we get 
$$b_{n+1}=b_{n-2}+b_{n-3}+b_{n-4}+b_{n-5}+ \cdots+b_3 +1.\tag{$2$}$$
Subtract $(1)$ from $(2)$ and rearrange a bit. We get 
$$b_{n+1}=b_n +b_{n-2}.$$ 
The initial conditions are $b_1=b_2=0$, and $b_3=1$. 
A: $b_n$ can be divided into 2 parts and then conquered. 
$b_n$ = 
        Number of such compositions with first term equals to 3 
      + Number of such compositions with first term larger than 3
For "Number of such compositions with first term equals to 3":
It's actually a bijection of b n-3. Think about it, if you remove that first term which equals to 3, it becomes the same as b n-3.
For "Number of such compositions with first term larger than 3":
It's actually a bijection of b n-1. If you subtract 1 from the first term. it becomes the same as b n-1 (It's got a recursive pattern here! You can analyze b n-1 in the same way as this one and divide it to similar two parts!).
So, the answer is b n = b n-3 + b n-1, which agrees with André Nicolas's answer.
Good luck with Math 461 at UW!
