5
$\begingroup$

How can I simplify the following expression?

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

$\endgroup$
  • 4
    $\begingroup$ Now if only the downvote was explained... what a jerk, that downvoter... $\endgroup$ – J. M. is a poor mathematician Oct 13 '11 at 11:13
6
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.