Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial problem

  1. Feb 27, 2010 #1
    Does [tex] \sum_{i=0}^n \binom{n-1+d-i}{d-i} = \binom{n+d}{d}?? [/tex]
  2. jcsd
  3. Mar 1, 2010 #2
    I'm gonna go ahead and assume that the sum on the LHS goes from 0 to d, not from 0 to n. In this case, yes. Because [tex]\binom {a}{b} = \binom{a}{a-b} [/tex], you can rewrite the LHS as

    [tex] \sum_{i=0}^d \binom{n-1+d-i}{n -1}[/tex]

    For the same reason, you can rewrite the RHS as [tex]\binom{n+d}{n} [/tex].

    Consider this hint: [tex]\binom{n-1+d-i}{n -1}[/tex] counts the number of subets of {1, 2, 3, ...., n+d-i-1} that are have size n -1. How many subsets of {1, 2, 3, ...., n+d} of size n have maximal maximal element n+d-i?
  4. Mar 5, 2010 #3
    I'm sorry I don't understand? Could you explain again?

    Thank you for your help
  5. Mar 6, 2010 #4
    Yes, you are correct. The summation should be from 0 to d.

    I have actually altered the problem slightly. I want to show that
    [tex] \sum_{k=0}^d \binom{n+d-k}{n} = \binom{n+d}{n}?? [/tex]

    I could maybe do this by induction on d as follows:

    d=0 : \binom{n}{n} = \binom{n+1}{n+1}
    assume true for all d
    \sum_{k=0}^{d+1} \binom{n+(d+1)-k}{n} = \binom{n+d+1}{n} + \sum_{k=1}^{d+1} \binom{n+d+1-k}{n}

    = \binom{n+d+1}{n} + \sum_{k=0}^{d} \binom{n+d-k}{n}

    and this is where I get stuck? ...any ideas?
  6. Mar 6, 2010 #5
    I get that this equals

    \binom{n+d+1}{n} + \binom{n+d+1}{n+1} = \binom{n+d+2}{n+1}

    is this correct?

    If so, how can I show that this equals [tex] \binom{n+d}{n} [/tex] ??
  7. Mar 7, 2010 #6
  8. Mar 9, 2010 #7
    This is not correct. The LHS you have here is not equal to the LHS you had before.

    More details on my response:

    You should know that if a and b are any two non-negative integers, [tex]\binom{a}{b} = \binom{a}{a - b}[/tex]. e.g., if I have 5 apples, the number of ways I can choose 2 apples is the same as the number of ways I can choose 3 apples. This is easy to see: to every choice of 2 apples, corresponds a choice of 3 apples (the apples that I didn't choose).

    This said, this means that we have:

    [tex]\sum_{i=0}^d \binom{n-1+d-i}{d-i} = \sum_{i=0}^d \binom{n-1+d-i}{(n-1 + d - i) - (d-i)} = \sum_{i=0}^d \binom{n-1+d-i}{n-1} [/tex]


    [tex] \binom{n+d}{d} = \binom{n+d}{(n+d) - d} = \binom{n+d}{n} [/tex]

    So in fact, we are trying to prove that:

    [tex]\sum_{i=0}^d \binom{n-1+d-i}{n-1} = \binom{n+d}{n} [/tex]

    Let's see how we can prove this. Let's first examine the RHS. What is this number? It's the number of ways we can choose n things from a set of n + d objects.

    Let's now look at the LHS. What does this count? Well, consider the set {1, 2, ..., n, n+1, ..., n +d}. As observed above, the RHS counts the number of size n subsets of this set.

    Aside from computing [itex]\binom{n+d}{n}[/itex], theres another way we can count these. Here's the idea: for each of n, n+1, n+2, ... , n+d, count the number of subsets of size n whose maximum element is that number, then add up the results.

    For example, if n = 3, d = 2, the number of subsets of size n with maximum element n, is 1, i.e. only the set {1,2,3}. The number of subsets with maximum element of size n+1 (4) is 3, i.e. {1,2,4}, {2, 3, 4}, {1, 3, 4}. The number of elements of subsets of size n with maximum element n + 2 = 5 is 6 (I won't list them). 1 + 3 + 6 = 10. You can easily check that [itex]\binom{3+2}{3} = 10[/itex], as expected.

    Now do you see where this is going? Can you show that \binom{n-1+d-i}{n -1} counts the number of size n subsets of {1, 2, ..., n+d} whose maximum element is n + d - i?
    Last edited: Mar 9, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook