5
$\begingroup$

How can I simplify the following expression?

$\sum_{k=1}^n \binom{n}{k}^2$

  • 4
    Now if only the downvote was explained... what a jerk, that downvoter...2011-10-13

3 Answers 3

1

$ \sum_{k=0}^n \binom{n}{k}^2 = \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} = \binom{2n}{n} $ The last equality is Vandermonde's identity. The first equality uses binomial coefficients symmetry $\binom{n}{k} = \binom{n}{n-k}$.

9

$\sum_{k=0}^n \binom{n}{k}^2 = \sum_{k=0}^n \binom{n}{k}\cdot\binom{n}{n-k} = \binom{2n}{n}$

The last equality can be understood using a combinatorial argument. You want to choose $n$ elements from a set of $2n$ elements, so you can decide in advance how many elements will you choose from the first $n$ , this is your $k$, and summing over $k$ you count the possibilities to choose $k$ elements from the first $n$ and $n-k$ from the last $n$. Hope it was clear. finally

$\sum_{k=1}^n \binom{n}{k}^2 = \binom{2n}{n} - 1$

  • 2
    This is in fact one of the simpler instances of the [Chu-Vandermonde convolution identity](http://mathworld.wolfram.com/Chu-VandermondeIdentity.html).2011-10-13
6

First write $(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k\tag{1}$ Then write $(1+x)^n=(x+1)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}\tag{2}$

Multiply (1) and (2) and equate coefficients of $x^n$ from both sides. Finally use $\binom{n}{0}=1$.

  • 0
    anon, +1 for your generalization which looks very nice. In school days I learnt to use this technique.2011-10-13