4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Off-topic question: How are identities such as this one derived? I could never wrap my head around that. o.o $\endgroup$ – Project Euler 57 Jun 7 '13 at 17:03
  • $\begingroup$ 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}$$ $\endgroup$ – Patrick Jun 7 '13 at 17:05
  • 1
    $\begingroup$ I think the term "indirect proof" is well-defined enough that you should say "less direct" rather than "indirect." $\endgroup$ – Thomas Andrews Jun 7 '13 at 17:26
  • $\begingroup$ Works for me. What's the definition of "indirect proof"? $\endgroup$ – Patrick Jun 7 '13 at 17:33
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Marc van Leeuwen Jun 7 '13 at 17:10
  • 1
    $\begingroup$ @MarcvanLeeuwen I find it more aesthetic that both $k$ and $n$ have $+1$. $\endgroup$ – Pedro Tamaroff Jun 7 '13 at 17:11

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.