# Combinatorics - simple proof

How to show that

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

Working on a problem that requires this. Hoping that there is a short/simple way to show that it is true within the bigger problem.

If you are asking for a combinatorial proof:

Consider the $$\binom {n+1}2$$ ways to choose $$2$$ elements from $$\{1,\cdots, n+1\}$$. Divide these into two types: those which contain $$n+1$$ and those which don't. There are $$n$$ of the former type and $$\binom n2$$ of the latter type.

$$\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}.$$

Just write out $${n \choose 2}=\frac 12n(n+1)$$ and the corresponding one for $$n+1$$ and do the algebra.

Algebraic proof:

$$\binom{n}{2}+n=\frac{n(n-1)}{2}+n=\frac{n(n-1)+2n}{2}=\frac{n(n+1)}{2}=\binom{n+1}{2}$$

Combinatoric proof:

In a set $$S$$ of $$n+1$$ objects choose one particular object $$x$$. Then there are $$n$$ pairs of distinct objects from $$S$$ in which one object in the pair is $$x$$. And there are $$\binom{n}{2}$$ pairs of distinct objects from $$S$$ in which neither object in the pair is $$x$$. But these two categories of pairs cover all $$\binom{n+1}{2}$$ pairs of distinct objects from $$S$$, and there is no overlap between them. So

$$\binom{n}{2}+n=\binom{n+1}{2}$$

Using the formula: $${n\choose r} + {n\choose r+1} = {n+1\choose r+1}$$

Thus: $${n\choose 2} + n = {n\choose 2} + {n \choose 1} = {n+1\choose 2}$$

Hence Proved.

Regarding proof of that formula:

$${n \choose r}+{n \choose r+1} = \frac{n!}{r!(n-r)!}+\frac{n!}{(r+1)!(n-r-1)!}$$
$$=\frac{n!}{(n-r)!}\bigg(\frac{1}{r!}+\frac{n-r}{(r+1)!}\bigg)$$
On solving we get:
$${n \choose r}+{n \choose r+1} = {n+1\choose r+1}$$

Consider the following:

Let $$n$$ be the number of dots in the bottom row. The red lines show that every pair of blue dots corresponds to exactly one yellow dot and vice versa. This shows that the number of possible blue pairs (which is of course $$n \choose 2$$) equals the number of yellow dots, and thus:

$$n \choose 2$$ equals the number of dots in a pyramid with base $$n-1$$.

But then it also immediately follows that the number of yellow and blue dots is the number of dots in a pyramid with base $$n$$, which by the above must equal $${n+1} \choose 2$$. Hence:

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