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

Homework Help: Changing the summation indexes in double sums.

  1. Sep 10, 2006 #1


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I have just made the following variable switch:

    [tex]\sum_{i=0}^n\sum_{j=0}^m\binom{n}{i}\binom{m}{ j}x^{i+j}=\sum_{k=0}^{n+m}\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}x^{k}[/tex]

    I know it's right, but is there a method I can use to prove without a shadow of a doubt that it is?
    Last edited: Sep 10, 2006
  2. jcsd
  3. Sep 10, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    They're both polynomials in x, just match up coefficients. For 0 < h < n+m, the coefficient of xh on the right is:

    [tex]\sum _{i=0} ^h \binom{n}{i}\binom{m}{h-i}[/tex]

    On the left, it's:

    [tex]\sum _{i=0} ^n \binom{n}{i}\binom{m}{h-i}[/tex]

    but [itex]\binom{m}{h-i}[/itex] is zero when i > h, so the above is really equal to:

    [tex]\sum _{i=0} ^h \binom{n}{i}\binom{m}{h-i}[/tex]

    which we've already seen to be the coefficient on the left side.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook