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!