Combinatorial explanation for why $n^2 = {n \choose 2} + {n+1 \choose 2}$

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?

Solution 1:

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

Solution 2:

$n^2$ is the number of non-negative integers less than $100_n$.

$2 {n \choose 2}$ is the number of non-negative integers with distinct digits less than $100_n$

${n \choose 1} = n$ is the number of non-negative integers with the same two digits less than $100_n$

Now, of course, we need an argument for ${n \choose 2} + n = {n + 1 \choose 2}$.

There are $n \choose 2$ ways to pick two elements from a set of $n$ elements. To find the number of ways to pick two elements from a set of $n+1$ elements, we include all of the possibilities from the $n$ subset along with each element of the $n$ subset paired up with the new element of the $n+1$ element.

Solution 3:

All the answers posted above is useful to a great extent. But, I am giving a visual proof (more than combinatorics).

What you want is $$\begin{align} &{n\choose 2}+{n+1\choose 2}=n^2\\ \implies&\frac {n(n-1)}2+\frac {(n+1)n}2=n^2\\ \implies&(1+2+\dots+(n-1))+(1+2+\dots+n)=n^2. \end{align}$$

Now, consider this square, colouring in this way. Here I am giving for $n=6$, it can be generalised easily, taking $n$-sided squares.

Here the number of coloured squares is $$\color{red}{6+5+4+3+2+1=\frac {6\times 7}2={6+1\choose 2}}.$$

Now colour the rest elements in this way,

So, here the number of coloured squares is $$\color{magenta}{5+4+3+2+1=\frac {5\times 6}2={6\choose 2}}.$$

And now, sum these up. What you get is

Here, the number of coloured squares is $$\color{blue}{6\times 6=6^2\text{[total number of squares]}}$$

So, ultimately, what we get is $${\color{red}{\text{no. of red coloured squares}}}+{\color{magenta}{\text{no. of pink coloured squares}}}={\color{blue}{\text{total number of squares}}}$$ $$\implies\color{red}{6+1\choose 2}+\color{magenta}{6\choose 2}=\color{blue}{6^2}$$

So, in generalised (taking $n$-sided squares), we have $$\implies\color{red}{n+1\choose 2}+\color{magenta}{n\choose 2}=\color{blue}{n^2}$$

Solution 4:

I don't see any direct explanation for this identity, but I can see something very simple if you apply ${n+1 \choose 2} = {n\choose2} + {n \choose 1}$.

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

$n^2$ is the number of ways to select two elements from a set of $n$, allowing duplicates, and taking order into account. $n \choose 2$ is the number of ways to select two non-duplicates from $n$, but not taking order into account. Because we don't take order into account, we have to double to get the total number of ways to select two distinct elements. We then just have to take care of the case where we select the same element twice, which is $n\choose1$.