Results 1 to 3 of 3

Math Help - Combinatorics problem - rescursion

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    8

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by tautology View Post
    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
    Last edited by tonio; October 18th 2009 at 05:17 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    8
    awesome! I got it thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with combinatorics problem
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: December 7th 2010, 04:35 PM
  2. Combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 11th 2010, 12:52 PM
  3. Combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 14th 2009, 11:48 AM
  4. Combinatorics Problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 30th 2008, 06:11 AM
  5. Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 5th 2008, 09:29 AM

Search Tags


/mathhelpforum @mathhelpforum