# Using Direct Proof. $1+2+3+\ldots+n = \frac{n(n + 1)}{2}$ [duplicate]

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 MillikanAug 27 '14 at 4:33

• yes that's it! should I delete this? – John Aug 27 '14 at 3:24
• It's up to you, I wouldn't worry about it, it'll probably get closed soon :) – Clive Newstead Aug 27 '14 at 3:25
• – Lucian Aug 27 '14 at 3:56
• @John, Just in case you feel difficult to decide on an answer: Feel free to choose any answer that best convinces you. – 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}$$

• 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. – Vincent Aug 27 '14 at 3:19
• 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$. – 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.