0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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}$

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

Consider the following:

enter image description here

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.