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.