How many ways can you express an integer as the sum of positive integers and each sum does not include any 2s?

Question

I came up across this question while self-studying combinatorics. I am supposed to derive a recurrence relation, however I am not sure how to approach or even start this problem. The order matters.

Answer 1

As Ross Millikan said in the comments, you're asking about integer compositions. If the order does not matter, the term is integer partitions.

The number of such compositions of $n$ that include no 2 is given by the recurrence $$a(n) = a(n-1) + a(n-2) + a(n-4)$$ for $n \ge 4$ with initial values $a(0) = a(1) = a(2) = 1$ and $a(3) = 2$, which is A005251 in the On-Line Encyclopedia of Integer Sequences.

The recurrence can be understood combinatorially: To build the desired compositions of $n$ from the previous sets,

(a) put $+1$ at the end of these compositions of $n-1$,

(b) make the last part of these compositions of $n-2$ longer by a length of 2 (e.g., $1+3 \mapsto 1+5$), and

(c) put $+4$ at the end of these compositions of $n-4$.

Step (a) produces all of these compositions of $n$ that end with $+1$, step (b) makes the ones that end $+3$, $+5$, $+6$, etc., (not $+4$ since these compositions don't have any 2s), and (c) produces that ones that end with $+4$. There are a few routine details you might want to work out to show this describes a bijection.

Answer 2

Divide the ways to express a number $n$ into those that end in $1$ and those that do not. To express $n+1$ you can take an expression of $n$ and add $+1$ to it. If an expression does not end in $+1$ you can increase the last addend by $1$. If the expression ends in $+1$ you can change it to $+3$. You get a pair of coupled recurrences. Starting from $4=3+1$ you can go to $5=3+1+1$ or $6=3+3$. From $4=1+3$ you get $5=1+4$ and $5=1+3+1$. You should be able to convince yourself that every expression can be built up uniquely this way.