2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Steven Stadnicki Dec 26 '10 at 0:21
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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