Different ways to come up with $1+2+3+\cdots +n=\frac{n(n+1)}{2}$

Question

I am trying to compile a list of the different ways to come up with the closed form for the sum in the title. So far I have the famous Gauss story, the argument by counting doubletons, and using generating functions. Is there any other (significantly) different way to discover the closed form?

To clarify, Gauss's method was to take $1+2+3+\dots+n$, write it backwards, and add it up.

Answer 1

One significantly different method is to bulldozer through using the Euler-Maclaurin formula:

$$\sum_{k=1}^nk=\int_0^nx\ dx+\frac12n+c=\frac12n^2+\frac12x+c$$

for some constant $c$. Plugging in $n=1$ reveals that $c=0$, so

$$\sum_{k=1}^nk=\frac12n^2+\frac12n$$

---

One can also try the hockey-stick identity:

$$\sum_{k=1}^nk=\sum_{k=1}^n\binom k1=\binom{n+1}2=\frac{n(n+1)}{2!}$$

(poor ones get a lame name) As you can see, each diagonal is the sum of the previous due to how Pascal's triangle is made.

---

Many more methods to computing this sum may be found in one of my favorite questions:

Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula

Answer 2

The difference equation $f(n) - f(n - 1) = n, f(0) = 0$ gives $f(n) = \sum_{x=1}^n x$. Solving that difference equation is pretty easy, and it shows that $f(n) = \frac{n(n + 1)}{2}$.

Answer 3

You have an education tag so perhaps you're looking for a less rigorous proof which might just make sense to students.

If you have the consecutive numbers $1,2,3,4,...,n$ in order then the average of the numbers is in the middle, that's the smallest number plus the largest divided by $2$.

$\text{average} = \frac{n+1}{2}$

Of course the main definition of the average is the sum of all the numbers divided by how many numbers there are.

$\text{average} = \frac{1+2+3+4+...+n}{n}$

Equating these two:

$\frac{1+2+3+4+...+n}{n} = \frac{n+1}{2}$

And therefore

$1+2+3+4+...+n = n\frac{n+1}{2}$

Answer 4

$f(x)=ax^2+bx+c$

$$f(0)=c=0$$

$$f(1)=a+b=1$$ $$f(2)=4a+2b=2+1=3$$

we have

$$4a+2b-2(a+b)=2a=3 -2=1$$ $$2a=1 \rightarrow a=\frac{1}{2}$$ $$b=\frac{1}{2} $$ $$f(x)=\frac{x^2+x}{2}$$

Answer 5

I want to add this proof because is very interesting, but I want to be clear stating that the merit is of the user @SimplyBeautifulArt in this post:

If you knew of the geometric series, you would know that

$$\frac{1-r^{n+1}}{1-r}=1+r+r^2+r^3+\dots+r^n$$

If we differentiate both sides, we have

$$\frac{nr^{n+2}-(n+1)r^{n+1}+r}{(1-r)^2}=1+2r+3r^2+\dots+nr^{n-1}$$

Letting $r\to1$ and applying L'Hospital's rule on the fraction, we end up with

$$\frac{n(n+1)}2=1+2+3+\dots+n$$

Answer 6

Since $(n+1)^2-n^2=2n+1$, we obtain: $$2(1+2+...+n)+n=2^2-1^2+3^2-2^2+...+(n+1)^2-n^2=(n+1)^2-1=n^2+2n,$$ which gives the answer.

Answer 7

Here is one with the use of Indeterminant Coefficients:

Starting with $$1+2+3+4+5+\cdots+n\tag1$$Assume it to be equal to $A+Bn+Cn^2+Dn^3+\cdots\&\text c$. Hence$$1+2+3+4+5+\cdots+n=A+Bn+Cn^2+Dn^3+En^4+\cdots\&\text c\tag2$$ Therefore, we also have$$1+2+3+4+\cdots+n+1=A+B(n+1)+C(n+1)^2+D(n+1)^3+\cdots\&\text c\tag3$$ Subtracting $(2)$ from $(3)$, we get$$n+1=B+C(2n+1)\tag4$$And equating coefficients, we have$$2C=1\\B+C=1\\\implies C=B=\dfrac 12,\ A=0$$ Therefore$$1+2+3+4+\cdots n=0+\dfrac 12n+\dfrac 12n^2=\dfrac {n^2+n}2\tag5$$

Answer 8

Consider $1+2+3+...n$. Add $1+2+3+...n$ to it. This counts the number of unit squares in an $n$ by $n$ square, but double counts $n$. So,

$$2(1+2+3+...n)=n^2+n$$

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

This figure aims to illustrate the argument.

Another way is by using area. Ignore the upper white area in the figure above. Then the area of the shape can be divided into an $n$ by $n$ right triangle and $n$, $1$ by $1$ right triangles so the total area is,

$$1+2+3+....n=\frac{n^2}{2}+n\frac{1(1)}{2}$$

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

Answer 9

This proof without words was entered and then deleted by @user170231, so I'm marking my answer community wiki. I don't think it counts as a duplicate of Gauss's proof.

Answer 10

Bearing in mind you asked for different ways:

$(n+1)^2 = n^2 + (2n + 1)$. $2n+1$ is the $n+1$th odd number. (the first odd number is $1 = 2*1 -1$; the second odd number is $3=2*2 -1$ and so on). From that we are inspired to and can easily verify that $m^2 = (m-1)^2 + (2m-1)$. So we can say with confidence that for any positive $m$ that $m^2$ is $(m-1)^2$ plus the $m$ th odd number.

Recursively that means $m^2$ is the sum of the first $m$ odd numbers.

So $\sum_{i=1}^m (2i -1) = m^2$ This the sum of the first $m$ odd numbers.

So $\sum_{i=1}^m (2i) = \sum_{i=1}^m(2i-1) + \sum_{i=1}^m 1= m^2 + m$. This is the sum of the first $m$ even numbers.

So $m^2 + m^2 + m$ is the sum of the first $m$ odd numbers plus the first $m$ even numbers. Or in other words the first $2m$ numbers.

So $\sum_{k = 1}^{2m}k = 2m^2 + m = m(2m + 1)$. Replace $2m$ with $n$ and you get

$\sum_{k=1}^n k= \frac n2(n+1)=\frac {n(n+1)}2$. Which proves it if $n$ is even.

If $n = 2m-1$ is odd then

$\sum_{k = 1}^n k =\sum_{k=1}^{2m-1}k = \sum_{k=1}^{2m}k - 2m = m(2m+1)- 2m = m(2m - 1)$.

Substituting $n = 2m-1$ we have $m = \frac{n+1}2$ and so $m(2m-1) = \frac{n+1}2n=\frac {n(n+1)}2$

That's different.

Answer 11

Note that we have the elementary sum

$$\sum_{\ell=1}^m(1)=m \tag 1$$

Hence, we have

$$\begin{align} \sum_{m=1}^n m&=\sum_{m=1}^n \sum_{\ell=1}^m(1)\\\\ &=\sum_{\ell=1}^n\sum_{m=\ell}^n (1)\\\\ &=\sum_{\ell=1}^n \left(n-\ell+1\right)\\\\ &=n(n+1)-\sum_{\ell=1}^n \ell\\\\ &=n(n+1)-\sum_{m=1}^n m\\\\ 2\sum_{m=1}^n m&=n(n+1)\\\\ \sum_{m=1}^n m&=\frac{n(n+1)}{2} \end{align}$$

as was to be shown.

Answer 12

One way I came up with is distributing the sum around a middle number, like this: $$1+2+3+4+5+6+7=(4-3)+(4-2)+(4-1)+4+(4+1)+(4+2)+(4+3)$$ We can do this for all sums which have odd number of terms. So, we get a formula for the sum, where $n$ is an odd number: $$1+2+3...+n=\dfrac{n(n+1)}{2}$$

For even number of terms, we can use this formula plus another number, which is even.

Answer 13

How many ways are there to pick an ordered pair of distinct numbers from $\{1,2,\ldots,n+1\}$?

1. There are $n+1$ ways to pick the first number and $n$ ways to pick the second one. This gives $n(n+1)$ unordered pairs. Divide by $2$, there are $\frac{n(n+1)}2$ ordered pairs.
2. Choose the larger number $k$ from $\{2,3,\ldots,n+1\}$, then choose the smaller one from $\{1,2,\ldots,k-1\}$. Hence there are $\sum_{k=2}^{n+1}(k-1)=1+2+\ldots+n$ ordered pairs.

Answer 14

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 1}^{n}k & = \sum_{k = 1}^{n}k^{\underline{1}} = \left.{1 \over 2}\,k^{\underline{2}}\,\right\vert_{1}^{n + 1} = {1 \over 2}\,\pars{n +1}^{\,\underline{2}}\ -\ {1 \over 2}\,1^{\underline{2}} = {1 \over 2}\,\pars{n + 1}n - {1 \over 2}\,1\times 0 = \bbx{\ds{n\pars{n + 1} \over 2}} \end{align}