1
$\begingroup$

This question already has an answer here:

Is there a standard expression for

$$\sum_{r=0}^{n}\binom nr^2$$

$\endgroup$

marked as duplicate by Community Feb 2 '16 at 19:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

6
$\begingroup$

Yes, $\sum_{r=0}^n\binom{n}{r}^2=\binom{2n}{n}$.

The proof is simple:

There are $\binom{2n}{n}$ paths from $(0,0)$ to $(n,n)$ going right or up.

On the other hand each path crosses the diagonal $(x,n-x)$ exactly once.

How many paths cross at $(r,n-r)$? Exactly $\binom{n}{r}\binom{n}{n-r}=\binom{n}{r}^2$.

Therefore $\sum\limits_{r=0}^n\binom{n}{r}^2=\binom{2n}{n}$

$\endgroup$
2
$\begingroup$

In fact, we have something slightly more general. Let $a,k$ be integers less than $n$. Then we have $$\sum_{i=0}^k \binom{a}{i} \binom{n-a}{k-i} = \binom{n}{k}.$$

The easiest way to see why this is true is to ask how many ways of picking $k$ elements from a set of size $n$ are there? On one hand, the answer is obviously $\binom{n}{k}$. On the other hand, we can split our set into two halves - one of size $a$, and one of size $n-a$ (how we do this is irrelevant). Then to get $k$ elements, you have to choose a certain amount, $i$, from the first set, and then $n-i$ from the second set. But we can do this for all $i$! Summing over $i$, we see that the two sides are equal.

$\endgroup$
0
$\begingroup$

Use Chu-Vandermonde's identity : $$ \sum_r {n \choose r}^2 = \sum_r {n \choose r} {n \choose n-r}={2n \choose n} $$

$\endgroup$

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