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?

  • $\begingroup$ 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. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.