# Simplify sum of products of binomials [closed]

Is there a way to simplify : $\sum_{i=1}^{n} {n \choose i} {m \choose i}$?

• If $m=n$, we get $\binom{2n}n$ – Simply Beautiful Art Mar 18 '17 at 12:39
• What's the value of $m$? – Icycarus Mar 18 '17 at 12:40
• @Icycarus what do you mean? m and n are random integers. – Nathan Mar 18 '17 at 12:42
• @SimplyBeautifulArt whats about case $m \neq n$? – Nathan Mar 18 '17 at 12:44
• @SimplyBeautifulArt You have seen it before, it is the Vandermonde convolution identity with the first term missing.$\sum_{i=1}^{n} \binom{n,i} \binom{m,i} =\binom{n+m,n}-1$ & it is very interesting IMHO :-) – Donald Splutterwit Mar 18 '17 at 13:02

When $n\leq m$ then $\sum_{k=0}^n \binom nk \binom m{k}$ counts all the ways to swap items between piles of $n$ and $m$ items; by doing counting selections of items in each pile to swap for each swap size ($k\in \{0..n\}$).   Also when $n>m$ it counts the same by the convention that $\binom {m}{r}=0$ for all $r>m$.

We could do this by gathering all the items into one pile of $n+m$ and count ways to sort them back into piles of $n$ and $m$ items.   This is $\binom {n+m}m$

Eg $\binom{5}2=10$

Thus as the count of ways to perform the same task must be the same:

$$\sum_{k=0}^n \binom n k\binom m k~=~ \binom {n+m}n ~=~ \binom {m+n}m ~=~ \sum_{k=0}^m \binom m k\binom n k$$

$~\\~\\~\\~\\~$

NB: Your series is indexed $1$, so does not include the term $\binom n0\binom m0$ which is 1.

$$\sum_{k=1}^n \binom n k\binom m k~=~ \binom {n+m}n-1 ~=~ \binom {m+n}m -1~=~ \sum_{k=1}^m \binom m k\binom n k$$

• Awesome interpretation, thanks! – Nathan Mar 18 '17 at 13:35

prove with induction that we get $$\sum_{i=1}^n\binom{n}{i}\binom{m}{i}={\frac { \left( m+1 \right) \left( n+m \right) !}{ \left( m+1 \right) !\,n!}}-1$$

• Thanks, right side can be simplified to: $\frac{(n+m)!}{m!n!}-1 = {{n+m} \choose {m}} - 1$. I am wondering how you come up with this right side? – Nathan Mar 18 '17 at 12:58
• i have this problem on my PC! i'm working with my students on combinatorics – Dr. Sonnhard Graubner Mar 18 '17 at 13:02
• The result on your PC can simplify. – Claude Leibovici Mar 18 '17 at 13:04
• ok i will note this thank you for the hint – Dr. Sonnhard Graubner Mar 18 '17 at 13:05
• Is there a way to came to the right side if a have no idea about how it looks? – Nathan Mar 18 '17 at 13:07