Changing the summation indexes in double sums.

[quasar987]

I have just made the following variable switch:

\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}

I know it's right, but is there a method I can use to prove without a shadow of a doubt that it is?

 

[AKG]

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

\sum _{i=0} ^h \binom{n}{i}\binom{m}{h-i}

On the left, it's:

\sum _{i=0} ^n \binom{n}{i}\binom{m}{h-i}

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

\sum _{i=0} ^h \binom{n}{i}\binom{m}{h-i}

which we've already seen to be the coefficient on the left side.