Thread: 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!

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 gives us an expression for by adding it 2 to the left of each sum, and each expression of gives us a new expression for 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








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 is always gotten that way, but that is easy: if the sum begins with a 2 it comes from , otherwise it comes from

Tonio

awesome! I got it thanks