# How can I simplify this expression involving binomial coefficients?

How can I simplify the following expression?

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

-
Now if only the downvote was explained... what a jerk, that downvoter... – J. M. Oct 13 '11 at 11:13

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$.

-
Déjà vu: I used this same exact approach in answering a generalization of this problem. – anon Oct 13 '11 at 11:27
anon, +1 for your generalization which looks very nice. In school days I learnt to use this technique. – Tapu Oct 13 '11 at 11:56

$$\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$$

-
This is in fact one of the simpler instances of the Chu-Vandermonde convolution identity. – J. M. Oct 13 '11 at 10:45

$$\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}$.

-