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!