Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

Question

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

Here is my solution:

Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. $2$-combinations can either be assembled both from $A$, both from $B$ or one from each. There are ${n \choose 2}$ from $A$ and ${n \choose 2}$ from $B$. For the mixed pair, each choice from $A$ can be coupled with $n$ choices from $B$ so the total is $n^2$.

Therefore ${2n\choose 2} = 2{n \choose 2} + n^2$

Is this correct. Is there any other combinatoric proof to solve this?

Answer 1

Just another way to think about it:

Let's find the coefficient of $x^2$ in the expansion of $(1+x)^{2n}$. On one side, it's equal to ${2n}\choose2$. On the other hand, it's equal to the coefficient of $x^2$ in the expansion of $(1+x)^n(1+x)^n$ which is equal to the sum of products of coefficients of $x^0$ and $x^2$, $x^1$ and $x^1$, and $x^2$ and $x^0$ in the expansion of $(1+x)^n$. That's equal to ${n\choose2}\cdot{ n\choose0}+{n\choose1}\cdot{ n\choose1}+{n\choose0}\cdot{ n\choose2}$ and the result follows.

Answer 2

Theorem: C(2n, 2) = 2C(n, 2) + n^2

Proof.

Suppose we have 2 groups, both of size n, which combine to make a class of size 2n, and we wish to know the number of ways we can choose 2 members from the class. This is represented by C(2n, 2).

There are C(n, 2) ways we can choose 2 students from a single group. Since there are 2 groups, there are 2C(n, 2) ways we can choose 2 students from a single group. Finally, there are n^2 ways to choose to members from the class where each member is from a different group, so there are 2C(n, 2) + n^2 ways to choose 2 members from the class of size 2n.

Therefore C(2n, 2) = 2C(n, 2) + n^2∎

Answer 3

There is a generalization of this fact that I cannot resist sharing. Here is how I came across it: Consider the scenario where you keep additively splitting a positive integer into two positive integers as a tree diagram, until you are left with only $1$'s as the leaves. Then you take the product of the two numbers at each branching and sum all such products. Remarkably, applying this process to $n$ will always yield $\binom{n}{2}$ as the final number. Try it with $8$ and you get $28$ every time. The inductive step of the strong induction argument for this fact uses the fact that, if you split $n=a+b$ then $$\binom{a}{2}+\binom{b}{2}+ab=\binom{a+b}{2}=\binom{n}{2}.$$ A combinatorial proof double counts the number of ways of choosing two people out of $n=a+b$ people. We can either choose $2$ out of the $a$ or $2$ out of the $b$ or $1$ from each. The original post asks for a combinatorial proof of this fact when $a=b.$