Combinatorial proof of $\binom{n^2}{2} = 2\left(\binom{\binom{n+1}{2}}{2}+\binom{\binom{n}{2}}{2}\right)$

Question

LHS = number of pairs of squares on an n×n grid of squares

I have tried conditioning on the diagonals to enumerate the RHS but nothing I have tried results in a disjoint exhaustive enumeration.

Another method I have attempted is to consider selecting columns and rows and picking two of their intersections in some prescribed method but nothing I have come up with works.

Answer 1

As you mentioned LHS is the number of ways to pick two coordinate elements in an $n\times n$ matrix. Now, you can do this in three ways:

1. Either the two coordinates belong to the same triangle (upper or lower, so $2$ options here) this can be done in $2\binom{\binom{n+1}{2}}{2}-\binom{n}{2}$ ways.
2. Or they belong to opposite parts (without being the same coordinate reflected), if so select both coordinates in the same triangle in $\binom{\binom{n}{2}}{2}$ ways and reflect one of the two coordinates (in $2$ ways).
3. The coordinates are literally in opposite sites of the main diagonal, this can be done in $\binom{n}{2}$ because you just have to pick one of them and reflect it.