11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just as there are many ways to derive a Faulhaber-like formula: Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula $\endgroup$ – Simply Beautiful Art Jan 20 '17 at 22:29
  • 1
    $\begingroup$ I presume this is folded into the 'counting doubletons' argument, but the proof-without-words at mathoverflow.net/a/8847/7092 is too good to let go by without a mention. $\endgroup$ – Steven Stadnicki Jan 20 '17 at 22:46
  • $\begingroup$ T^T The Gauss is really killing the answers, so I tried to clarify it. $\endgroup$ – Simply Beautiful Art Jan 20 '17 at 23:00
  • $\begingroup$ How come nobody mentioned induction yet? $\endgroup$ – rtybase Jan 20 '17 at 23:31
  • $\begingroup$ @rtybase That assumes we know the solution, and someone did mention it, but the question asks us different way to discover the closed form? $\endgroup$ – Simply Beautiful Art Jan 21 '17 at 2:02

14 Answers 14

15
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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!}$$

enter image description here

(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

$\endgroup$
  • $\begingroup$ You seem to love Euler - Maclaurin Formula ... Literally every answer of your contains that.... XD +1 $\endgroup$ – user399078 Feb 2 '17 at 12:02
  • 1
    $\begingroup$ I use my tools effectively? $\endgroup$ – Simply Beautiful Art Feb 2 '17 at 12:06
  • $\begingroup$ What do you mean ??? $\endgroup$ – user399078 Feb 2 '17 at 12:07
  • 1
    $\begingroup$ I have a lot of different random things like that, and I use it. :-) $\endgroup$ – Simply Beautiful Art Feb 2 '17 at 12:23
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Haha, thanks for the reference! (And an alternative way of doing the same thing is to have $r=e^x$ and differentiate w.r.t. $x$. $\endgroup$ – Simply Beautiful Art Jan 20 '17 at 23:02
  • $\begingroup$ If you put it as an answer I can quit this post to not repeat yours :-) $\endgroup$ – MonsieurGalois Jan 20 '17 at 23:03
  • 1
    $\begingroup$ Nah, you keep it. I already posted 2 answers in one. (and shall upvote when I get votes to use :3) $\endgroup$ – Simply Beautiful Art Jan 20 '17 at 23:06
  • $\begingroup$ Btw, I don't think you should be afraid of posting answers you've seen from other people. :-) $\endgroup$ – Simply Beautiful Art Jan 21 '17 at 12:35
  • $\begingroup$ Well, I wanted to point the user that have the merit and that in that post are more proofs about the Gauss sum. $\endgroup$ – MonsieurGalois Jan 21 '17 at 18:05
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would the cowardly downvoter dare to comment? $\endgroup$ – Mark Viola Apr 5 '17 at 14:08
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How to know that $f(x)=ax^2+bx+c$? Other than that, good interpolation. $\endgroup$ – Simply Beautiful Art Jan 20 '17 at 23:00
  • 1
    $\begingroup$ can i say that f(x)+(x+1)=f(x+1) => f"(x)=f"(x+1) = constant so it is at most a a second-degree polynomial $\endgroup$ – Slei. Jan 20 '17 at 23:06
  • $\begingroup$ Haha, could also see the last link in my answer. $\endgroup$ – Simply Beautiful Art Jan 20 '17 at 23:07
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Assuming the result is analytic. :-) $\endgroup$ – Simply Beautiful Art Jan 21 '17 at 2:03
1
$\begingroup$

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.

enter image description here

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

$\endgroup$
1
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ I guess we could argue all day about whether or not this is a duplicate of Gauss's proof, but either way, I think it's strongly related. $\endgroup$ – Simply Beautiful Art Jan 21 '17 at 2:03
  • $\begingroup$ It is a duplicate of gauss's proof but so what. It's an original way to present the proof and a very aesthetic a clever presentation. $\endgroup$ – fleablood Jan 21 '17 at 2:12
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Rather than $1+2+3+\dots+n=\frac{n(n+1)}2$, I've always seen faces light up so much more when they find the sum of odd numbers. $\endgroup$ – Simply Beautiful Art Jan 21 '17 at 2:06
  • $\begingroup$ I remember discovering that on my own and being impressed. But it was decades before I realized in n^2 + 2n +1 that 2n+1 was ,duh, the next odd number. Staring my in nose. $\endgroup$ – fleablood Jan 21 '17 at 2:09
  • $\begingroup$ Lol. I found it the other way. Noting that $(n+1)^2=n^2+2n+1$, I deduce the sum of odds... a very backwards upbringing I suppose. $\endgroup$ – Simply Beautiful Art Jan 21 '17 at 2:13
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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}

$\endgroup$
0
$\begingroup$

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

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.