combinatorics - Combinatorial proof of $binom{nk}{2}=kbinom{n}{2}+n^2binom{k}{2}$

This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good example for future reference.

Also, there was just a flat-out wrong answer which had a couple of upvotes, so I thought to give my own possible proof and sort of 'reopen' the question that was left. Hopefully this time the question will have enough context to stay alive.

As a side note: the given right side does not appear symmetric between $k$ and $n$. However, when $\binom{m}{2}=m(m-1)/2$ is inserted and the products expanded, only symmetric terms remain uncancelled. Rendering the right side as $k^2\binom{n}{2}+n\binom{k}{2}$ would give the same cancellations and the same net value.

Proof

Suppose you have a grid of $n\times k$ dots. Firstly, the amount of ways to connect any two dots is $\binom{nk}{2}$. Now consider the right-hand side. We can split the cases for which the connected dots are on the same column, row, or are in both different columns and rows.

If the two connected dots are in the same column, we can choose two points from any two different rows in $\binom{n}{2}$ ways, and we have $k$ columns for which the two points can be on the same column, which gives a total of $k\binom{n}{2}$ options. The same argument holds for constant rows: $n\binom{k}{2}$.

Now if neither the row nor the column can stay constant, we can pick any point in $nk$ ways, and choose the second point from the remaining $(n-1)(k-1)$ points; one column and one row will be unavailable. This gives us $\frac{nk(n-1)(k-1)}{2}$ options, as we have to rule out the double counting.

We will now show (algebraically) that $n\binom{k}{2}+\frac{nk(n-1)(k-1)}{2}=n^2\binom{k}{2}$.

We have that $\binom{k}{2}=\frac{k(k-1)}{2} =\frac{nk(n-1)(k-1)}{2n(n-1)} \iff n(n-1)\binom{k}{2}=\frac{nk(n-1)(k-1)}{2}=n^2\binom{k}{2}-n\binom{k}{2}$ which leads to the equation above.

Combining these cases gives $\binom{nk}{2}=k\binom{n}{2}+n\binom{k}{2}+\frac{nk(n-1)(k-1)}{2} = k\binom{n}{2}+n^2\binom{k}{2}$

If there are any mistakes or improvements on the arguments, please feel free to point them out.

Answer

I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $\binom{nk}{2}$ ways.

Alternatively, both are in the same group of $n$ which has $\binom{k}{1} \cdot \binom{n}{2}$ possibilities, or they are in different groups of $n$, which has $\binom{k}{2} \binom{n}{1}^2$ possibilities.

Therefore, $\binom{nk}{2} = k \binom{n}{2} + n^2 \binom{k}{2}$