Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I simplify the following expression?

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

share|improve this question
4  
Now if only the downvote was explained... what a jerk, that downvoter... –  J. M. Oct 13 '11 at 11:13

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
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$$

share|improve this answer
2  
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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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