# Prove $\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}$

How to prove that $$\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}=\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}$$ ?

I tried to break the right side of equation down: $$\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}=\sum_{i=0}^{i=x} {x+1 \choose i} {y+i \choose x}+{x+1 \choose x+1} {y+x+1 \choose x}$$

Then I tried Vandermonde's Identity: $${y+x+1 \choose x} = \sum_{i=0}^{i=x} {y+1 \choose i}{x \choose x-i}$$

Now I am totally lost. Can someone please tell me how to prove this equation?

• Just split the $\dbinom{x+1}{i}$ on the right hand side into $\dbinom{x}{i}+\dbinom{x}{i-1}$, and use this to split the sum into two sums. Rewrite the second sum by substituting $i$ for $i-1$, and tweak the boundaries of the summation (by discarding/adding zero addends). You'll get exactly the left hand side. – darij grinberg Jul 25 '16 at 15:15

This is very easy to prove using the integral representation of binomial coefficients. Suppose we are trying to prove that

$$\sum_{k=0}^n {n\choose k} {m+k\choose n} + \sum_{k=0}^n {n\choose k} {m+1+k\choose n} = \sum_{k=0}^{n+1} {n+1\choose k} {m+k\choose n}.$$

Use the two integrals $${m+k\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+k}}{z^{n+1}} \; dz$$ and $${m+k+1\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1+k}}{z^{n+1}} \; dz.$$

This yields for the LHS the following sum consisting of two terms: $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{n+1}} \sum_{k=0}^n {n\choose k} (1+z)^k\; dz \\ + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{n+1}} \sum_{k=0}^n {n\choose k} (1+z)^k\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{n+1}} (2+z)^n \; dz + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{n+1}} (2+z)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{n+1}} (2+z)^{n+1} \; dz.$$

For the RHS we get the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{n+1}} \sum_{k=0}^{n+1} {n+1\choose k} (1+z)^k\; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{n+1}} (2+z)^{n+1} \; dz.$$

The integrals on the LHS and on the RHS are the identical, QED.

A similar calculation is at this MSE link.

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

• wow! this was great! – Aaron Maroja Sep 22 '14 at 20:29
• Brilliant! Thank you! – mutian Sep 23 '14 at 23:27