Combinatorics problem - rescursion

• October 18th 2009, 02:24 PM
tautology
Combinatorics problem - rescursion
Hey everyone, first post! I have been stuck on this problem for a very long time and can't see to make any headway.

For n>=1, let h_n be the number of ways to express n as the sum of a sequence of positive integers which are each at least 2. Prove that h_n = h_n-1 + h_n-2 for n>=3.

As usual I have listed out some examples to help myself and I will list them here.

n=1 | 0 |
n=2 | 1 | 2
n=3 | 1 | 3
n=4 | 2 | 2+2; 4
n=5 | 3 | 2+3; 3+2; 5
n=6 | 5 | 2+2+2; 3+3; 4+2; 2+4; 6

I have tried to do a couple of different things but none of them seem to pan out.

I have noticed that for some h_n, if for each sequence in h_n-2 you put a 2+ in front of the first number, and for each h_n-1 sequence you add one to the first term in each sequence, you generate all the sequences of h_n. However, I don't know how I would do a proof with that.

Any help to get me in the right direction? Thanks!
• October 18th 2009, 04:05 PM
tonio
Quote:

Originally Posted by tautology
Hey everyone, first post! I have been stuck on this problem for a very long time and can't see to make any headway.

For n>=1, let h_n be the number of ways to express n as the sum of a sequence of positive integers which are each at least 2. Prove that h_n = h_n-1 + h_n-2 for n>=3.

As usual I have listed out some examples to help myself and I will list them here.

n=1 | 0 |
n=2 | 1 | 2
n=3 | 1 | 3
n=4 | 2 | 2+2; 4
n=5 | 3 | 2+3; 3+2; 5
n=6 | 5 | 2+2+2; 3+3; 4+2; 2+4; 6

I have tried to do a couple of different things but none of them seem to pan out.

I have noticed that for some h_n, if for each sequence in h_n-2 you put a 2+ in front of the first number, and for each h_n-1 sequence you add one to the first term in each sequence, you generate all the sequences of h_n. However, I don't know how I would do a proof with that.

Any help to get me in the right direction? Thanks!

Try the following: every expression of $h_{n-2}$ gives us an expression for $h_n$ by adding it 2 to the left of each sum, and each expression of $h_{n-1}$ gives us a new expression for $h_n$ by adding 1 to the leftmost summand in each sum, when we order the sums in each case just as you did: in increasing order from left to right.

For example, for $n = 6,7,8:$

$6:\ 2 + 2 + 2, \ 2 + 4, \ 3 + 3, \ 4 + 2,\ 6$

$7:\ 2 + 2 + 3,\ 2 + 3 + 2, \ 2 + 5, \ 3 + 2 + 2, \ 3 + 4, \ 4 + 3, \ 5 + 2, \ 7$

$8:\ 2 + 2 + 2 + 2, \ 2 + 2 + 4, \ 2 + 3 + 3, \ 2 + 4 + 2, \ 2 + 6, \ *3 + 2 + 3*, \ *3 + 3 + 2*$
$\ *3 + 5*, \ *4 + 2 + 2*, \ *4 + 4*, \ *5 + 3*, \ *6 + 2*, \ *8*$

Note that the sums between *.* are constructed from sums of 7 by adding 1 to each leftmost number there, whereas the other sums are constructed from the ones of 6 by adding 2 in the left to each sum there.

The only thing left there is to prove that every sum for $h_n$ is always gotten that way, but that is easy: if the sum begins with a 2 it comes from $h_{n-2}$, otherwise it comes from $h_{n-1}$

Tonio
• October 18th 2009, 08:36 PM
tautology
awesome! I got it thanks