An exercise in the first chapter of Discrete Mathematics, Elementary and Beyond asks for a proof of the following identity:
$$
{n \choose 2} + {n+1 \choose 2} = n^2
$$
The algebraic solution is obvious to me, but less so the combinatorial logic. I think the right-hand side relates to choosing one of n elements twice in a row to produce a set of two elements, including the possibility of duplicate elements (for instance, one could choose the nth element twice in a row). However, given that the sets discussed thus far do contain duplicate elements, it's odd to then interpret n^2 as a representation of such a set. I'm not too sure what the two parts of the left side mean when taken together, either. How can I think about this intuitively based on the combinatorial meanings of the individual terms?
Best Answer
How many pairs of numbers $(k,j)$ are there for $1\leqslant j,k\leqslant n$? The obvious solution is $n^2$. The other solution is to count those with $k<j$ and those with $k\geqslant j$. The first number is seen to be $$\binom n2 $$ The second is $$\binom n2+\binom n1=\binom{n+1}2$$
Since choosing a subset of two elements of an $n+1$-sized set amounts to choosing either $2$ from the first $n$ elements or fixing $n+1$ and choosing one from the first $n$ elements.
(The geometric idea is that a square composed of $n^2$ little squares of size $1\times 1$ is a union of two triangles consisting of $\binom n2$ and $\binom{n+1}2$ little squares.)