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

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?

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

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.

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

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

• nice work$\Large{+}\color{red}{+}\color{pink}{+}$ – Software Jun 9 '13 at 10:28

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

• Off-topic question: How are identities such as this one derived? I could never wrap my head around that. o.o – Project Euler 57 Jun 7 '13 at 17:03
• Induction is one method, which you now have some practice in so it's worth the attempt. An option avoiding induction is to say $$S=1+2+\cdots+n$$ $$2S=(n+1)+\cdots+(n+1)=n(n+1)$$ $$S=\frac{n(n+1)}{2}$$ – Patrick Jun 7 '13 at 17:05
• I think the term "indirect proof" is well-defined enough that you should say "less direct" rather than "indirect." – Thomas Andrews Jun 7 '13 at 17:26
• Works for me. What's the definition of "indirect proof"? – Patrick Jun 7 '13 at 17:33

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.

• I prefer $\sum_{i=0}^{n-1}\binom ik=\binom n{k+1}$, so that it holds for $k=0$ too (and also somewhat better matches the question). – Marc van Leeuwen Jun 7 '13 at 17:10
• @MarcvanLeeuwen I find it more aesthetic that both $k$ and $n$ have $+1$. – Pedro Tamaroff Jun 7 '13 at 17:11