Is $\sum_{i=1}^{n-1}i=\binom{n}{2}$?

Question

How can I show that

$$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$

This is what I have tried, but I do not know if it is correct:

Proof.

Let $n=2$. Then,

$$ \begin{align} \sum_{i=1}^{1}i&=1\text{, and}\\ \binom{2}{2}&=1. \end{align} $$

Hence, it holds. Assume that this is true for $k$. Then, we show that it is also true for $k+1$:

$$ \begin{align} \sum_{i=1}^{k}i=k+\sum_{i=1}^{k-1}i&=k+\binom{k}{2}\\ &=k+\frac{k!}{2(k-2)!}\\ &=k+\frac{k(k-1)}{2}\\ &=\frac{k(k+1)}{2}\\ &=\frac{(k+1)!}{2!(k-1)!}=\binom{k+1}{2}.\square \end{align} $$

Also, proofs by induction are confusing to write. Is there a standard "skeleton" for them I can use?

Answer 1

An "indirect" proof would be to use the fact that $$\sum_{k=1}^{n}k = \frac{n(n+1)}{2}$$

Answer 2

In general $$\sum_{i=1}^{n}\binom{i}{k}=\binom{n+1}{k+1}$$

Yours is the case $k=1$. You can prove this in the same way you did the case $k=1$, by using Pascal's rule.

Answer 3

If proof by induction is required, yours is fine.

We can alternately give a combinatorial proof. We have the $n$ numbers $1,2,\dots,n$ and want to choose $2$ of them. By definition this can be done in $\binom{n}{2}$ ways. Let us count the number of choices of any two numbers another way.

Perhaps the smaller of the two numbers chosen is $1$. Then the other number can be chosen in $n-1$ ways.

Perhaps the smaller of the two numbers chosen is $2$. Then the other number can be chosen in $n-2$ ways.

Perhaps the smaller of the two numbers chosen is $3$. Then the other number can be chosen in $n-3$ ways.

Continue in this way. The last possibility is that the smaller of the two numbers chosen is $n-1$. Then the other number can be chosen in $1$ way only.

Thus the number of possible choices of two numbers is $$(n-1)+(n-2)+(n-3)+\cdots +2+1,$$ which is precisely $\sum_{k=1}^{n-1}k$.

Answer 4

Hint:let $a_n=1+2+3+\dots+n$ then we have $$a_{n+1}-a_{n}=(1+2+3+\dots+n+n+1)-(1+2+3+\dots+n)=n+1 \color{red}{\to}$$$$ a_{n+1}-a_{n}=n+1 $$ easily by recursive relation we can find $a_n$ see here linear recurrence relation

Answer 5

A way to derive formulas like this that is easily remembered (to answer the comment "How are identities such as this one derived?"):

Consider that $$\sum_{k=1}^n (2k-1) = \sum_{k=1}^n \Big(k^2 - (k-1)^2\Big) $$ $$= 1^2 - 0^2 + 2^2 - 1^2 + 3^2 - 2^2 \pm ... \pm n^2 - (n-1)^2=n^2.$$

Together with $\sum_{k=1}^n 1 = n$ this immediately gives $$\sum_{k=1}^n k = \frac{n^2 + n}{2}.$$

It could be argued that the "telescoping sum" above requires induction to justify formally, but it seems more intuitive than the sum $\sum_{k=1}^n k$ itself.

Answer 6

How many unordered pairs of $n$ elements are there?

One can pair the first element with any of $n-1$ others.

One can pair the second element with any of $n-2$ other (besides the first one, which was already listed above).

One can pair the third element with any of $n-3$ other (besides the first two, which were already listed above).

One can pair the fourth element with any of $n-4$ other (besides the first three, which were already listed above).

 . . . and so on . . . . . .