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.

Show that $\binom{2n}{2} = 2 \binom{n}{2}+n^2$.

LHS: This is the number of pairs of $2n$ distinct elements.

RHS: We can rewrite this as $2 \binom{n}{2}+ \binom{n}{1} \binom{n}{1}$. So you can divide up the $2n$ distinct elements into two subsets of $n$ elements. Then pick an element from each of these subsets to form a pair. Or you can just choose $2$ elements from the $n$ element subset (and multiply by $2$ since order matters).

Is this the correct idea?

share|improve this question
    
Your last note isn't quite right - but you're close. If you divide your set of $2n$ elements into 2 sets of $n$ elements, then there are three different ways of choosing 2 elements from your original set: they can both come from the first set (in $n\choose 2$ ways), they can both come from the second set (also in $n\choose 2$ ways), or one can come from each set (in $n\times n$ ways). Summing these gives the RHS of your formula. Now, can you see how this would generalize to the case of uneven splits? –  Steven Stadnicki Dec 26 '10 at 0:21

2 Answers 2

up vote 2 down vote accepted

Looks good to me. Also you could just work numerically: ${{2n} \choose 2}=\frac{1}{2} \times 2n(2n-1)=n(2n-1)=2n^2-n=n(n-1)+n^2=2{n \choose 2}+n^2$.

share|improve this answer
    
+1,Precise and to the point. –  Quixotic Dec 26 '10 at 13:40

$2n \choose 2$ is the sum of numbers from $1$ to $2n-1$, which is the sum of even numbers from $2$ to $2(n-1)$, which is $2{n\choose 2}$, and odd numbers from $1$ to $2n-1$. The latter is of course $n^2$.

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.