This question already has an answer here:

I need help proving this statement. Any help would be great!


marked as duplicate by Clive Newstead, Michael Albanese, Mark Fantini, Claude Leibovici, Ross Millikan Aug 27 '14 at 4:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ yes that's it! should I delete this? $\endgroup$ – John Aug 27 '14 at 3:24
  • $\begingroup$ It's up to you, I wouldn't worry about it, it'll probably get closed soon :) $\endgroup$ – Clive Newstead Aug 27 '14 at 3:25
  • $\begingroup$ See Faulhaber's formulas. $\endgroup$ – Lucian Aug 27 '14 at 3:56
  • $\begingroup$ @John, Just in case you feel difficult to decide on an answer: Feel free to choose any answer that best convinces you. $\endgroup$ – Gary Moore Aug 27 '14 at 3:57

Here is an approach.

$$ s_n =1+2+3+\dots+(n-1)+n \\ s_n =n+(n-1)+(n-2)+\dots+1 . $$

Adding the above gives

$$2s_n = (1+n)+(2+(n-1))+(3+(n-2))+\dots+(1+n) $$

$$ =(1+n)+(1+n)+\dots+(1+n) $$

The above is nothing but adding $(1+n)$ n times and the result follows

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


As an alternative to induction you can try this:

Let $S_n = 1 + 2 + \ldots + n$.

Then $2S_n = \color{red}{1 + 2 + \ldots + n} + \color{blue}{1 + 2 + \ldots + n} = (\color{red}{1} + \color{blue}{n}) + (\color{red}{2} + \color{blue}{n-1}) + \ldots + (\color{red}{n} + \color{blue}{1}) = n(n+1)$

Therefore $$S_n = \frac{n(n+1)}{2}$$


Hint. $$\def\b{\!\color{red}{\bullet}}\def\c{\!\circ} \matrix{\b&\c&\c&\c&\c&\c&\c\cr\b&\b&\c&\c&\c&\c&\c\cr \b&\b&\b&\c&\c&\c&\c\cr\b&\b&\b&\b&\c&\c&\c\cr \b&\b&\b&\b&\b&\c&\c\cr\b&\b&\b&\b&\b&\b&\c\cr}$$

  • $\begingroup$ Could you explain this as a direct proof? I'm not saying you're wrong, if it is I would love to be able to use it in the future. $\endgroup$ – Vincent Aug 27 '14 at 3:19
  • $\begingroup$ Probably depends what you mean by a "proof". In practice I personally am perfectly happy with the concept "a proof is any argument which can be expected to be completely convincing to its intended audience" (no objections from logicians please). So, I think the diagram makes the result clear for $n=6$, and I suggest you then add an explanation in words as to why a similar diagram will work for any $n$. $\endgroup$ – David Aug 27 '14 at 3:23

Suppose you have a round robin tournament with $n+1$ players $a_1,\ldots,a_{n+1}$ who play one another exactly once. Let $S$ be the number of matches.

Each of the ${n+1}$ players plays the other $n$ players but you don't want to count duplicates (i.e. $a_1$ plays $a_2$ is the same match as $a_2$ plays $a_1$) so $S=\frac{1}{2}(n+1)n$.

On the other hand, you can enumerate the matches as follows:

  • $n$ matches involving $a_1$,
  • $n-1$ matches involving $a_2$ without involving $a_1$,
  • $n-2$ matches involving $a_3$ without involving $a_2,a_1$,
  • $\cdots$
  • 1 match involving $a_n$ without involving $a_{n-1},\ldots,a_1$.

So $S=n+(n-1)+\cdots+1$.


Below is a direct, inductive proof:

For $n=1$ we have $$1 = \frac{1(1+1)}{2}.$$ To proceed from $n=k$ to $n = k+1$ note that $$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2},$$ qed.


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