C F Gauss, on how to add all numbers of 1 to 100?

[CaptainBlack]

Mark on Yahoo answers asks:

Carl gauss 1777 1855 , on how to add all numbers of 1 to 100?

I can only add from 1 to 100 in order, apparently he could add lighteningly fast, and backwards, can anyone explain how in the confines of one message on here please

Allegedly his method was something like:

$(1+100)+(2+99)+ ... +(99+2)+(100+1)=2(1+2+...+100)$

But the left hand side is $101\times 100$, so $1+2+..100=101\times 100/2$

(Like Marlow's Dr Faustus he could sum them forwards and backwards - but had no need of anagramatisation)

CB

 

[Nono713]

This also works for any sum:

$\displaystyle \sum_{k = 1}^{n} k = 1 + 2 + \cdots + n $

This sum can be reorganized in this fashion:

$\displaystyle \left ( 1 + \left ( n \right ) \right ) + \left ( 2 + \left ( n - 1 \right ) \right ) + \cdots + \left (n + \left (1 \right ) \right )$

This produces $n$ sums of $n + 1$, so the total sum is $n(n + 1)$. But note that this goes through the list twice, from the left and from the right (for instance, $1$ is added to $n$ at the beginning and at the end). So this is actually twice the sum we need, we conclude:

$\displaystyle \sum_{k = 1}^{n} k = \frac{n(n + 1)}{2}$

$n = 100$ can then be easily calculated from the formula, just as can $n = 4885$ or $n = 6$ ;)

 

[QuestForInsight]

I would like to share two more ways of doing this.

Proof #0 (Notice that what Gauss did is basically this):

$\begin{aligned} \displaystyle & \sum_{0 \le k \le n}k = \sum_{0 \le k \le n}(n-k) = n\sum_{0 \le k \le n}-\sum_{0 \le k \le n}k \\& \implies 2\sum_{0 \le k \le n}k = n(n+1) \implies \sum_{0 \le k \le n}k = \frac{1}{2}n(n+1).\end{aligned}$

Proof #1 (Now try that with $\sum_{0 \le k \le n}k^2$ and you will be pleasantly surprised):

$\begin{aligned} \displaystyle & \sum_{0 \le k \le n}k^2 = \sum_{0 \le k \le n}(n-k)^2 = n^2\sum_{0 \le k \le n}-2n\sum_{0 \le k \le n}k+\sum_{0 \le k \le n}k^2 \\& \implies 2n\sum_{0 \le k \le n}k = n^2(n+1) \implies \sum_{0 \le k \le n}k = \frac{1}{2}n(n+1).\end{aligned}$

Proof #2 (Writing it as a double sum and switching the order of summation):

$\begin{aligned}\displaystyle & \begin{aligned}\sum_{1 \le k \le n}k & = \sum_{1 \le k \le n}~\sum_{1 \le r \le k} = \sum_{1 \le r \le n} ~\sum_{r \le k \le n} = \sum_{1 \le r \le n}\bigg(\sum_{1 \le k \le n}-\sum_{1 \le k \le r-1}\bigg) \\& =\sum_{1 \le r \le n}\bigg(n-r+1\bigg) = n\sum_{1 \le k \le n}-\sum_{1 \le k \le n}k+\sum_{1 \le k \le n}\end{aligned} \\& \implies 2\sum_{1 \le k \le n}k = n^2+n \implies \sum_{1 \le k \le n}k = \frac{1}{2}n(n+1), ~ \mathbb{Q. E. D.}\end{aligned}$

 

[MarkFL]

Warning: extremely long-winded post ahead! (Malthe)

Here are two closely related methods to derive the formulas for summations of sequences of natural number powers of integers from 0 - n.

Method 1: A "bottom-up" approach...

We may state:

$\displaystyle\sum_{k=0}^n(k)=\sum_{k=0}^n(k+1)-(n+1)$

$\displaystyle\sum_{k=0}^n(k)=\sum_{k=0}^n(k)+\sum_{k=0}^n(1)-(n+1)$

$\displaystyle0=\sum_{k=0}^n(1)-(n+1)$

$\displaystyle\sum_{k=0}^n(1)=n+1$

Now we may compute:

$\displaystyle\sum_{k=0}^n(k)$

We may state:

$\displaystyle\sum_{k=0}^n\left(k^2 \right)=\sum_{k=0}^n\left((k+1)^2 \right)-(n+1)^2$

$\displaystyle\sum_{k=0}^n\left(k^2 \right)=\sum_{k=0}^n\left(k^2+2k+1 \right)-(n+1)^2$

$\displaystyle\sum_{k=0}^n\left(k^2 \right)=\sum_{k=0}^n\left(k^2 \right)+2\sum_{k=0}^n(k)+\sum_{k=0}^n(1)-(n+1)^2$

$\displaystyle2\sum_{k=0}^n(k)=-\sum_{k=0}^n(1)+(n+1)^2$

Now, using our previous result, we have:

$\displaystyle2\sum_{k=0}^n(k)=-(n+1)+(n+1)^2$

$\displaystyle2\sum_{k=0}^n(k)=(n+1)\left(-1+(n+1) \right)$

$\displaystyle2\sum_{k=0}^n(k)=(n+1)(n)$

$\displaystyle\sum_{k=0}^n(k)=\frac{n(n+1)}{2}$

Now we may continue and find:

$\displaystyle\sum_{k=0}^n\left(k^2 \right)$

$\displaystyle\sum_{k=0}^n\left(k^3 \right)=\sum_{k=0}^n\left((k+1)^3 \right)-(n+1)^3$

$\displaystyle\sum_{k=0}^n\left(k^3 \right)=\sum_{k=0}^n\left(k^3+3k^2+3k+1 \right)-(n+1)^3$

$\displaystyle\sum_{k=0}^n\left(k^3 \right)=\sum_{k=0}^n\left(k^3 \right)+3\sum_{k=0}^n\left(k^2 \right)+3\sum_{k=0}^n(k)+\sum_{k=0}^n(1)-(n+1)^3$

$\displaystyle3\sum_{k=0}^n\left(k^2 \right)=-3\sum_{k=0}^n(k)-\sum_{k=0}^n(1)+(n+1)^3$

Using our previous results, we have:

$\displaystyle3\sum_{k=0}^n\left(k^2 \right)=-3\left(\frac{n(n+1)}{2} \right)-(n+1)+(n+1)^3$

$\displaystyle3\sum_{k=0}^n\left(k^2 \right)=(n+1)\left(-\frac{3n}{2}-1+(n+1)^2 \right)$

$\displaystyle3\sum_{k=0}^n\left(k^2 \right)=(n+1)\left(-\frac{3n}{2}-1+n^2+2n+1 \right)$

$\displaystyle3\sum_{k=0}^n\left(k^2 \right)=(n+1)\left(n^2+\frac{n}{2} \right)$

$\displaystyle3\sum_{k=0}^n\left(k^2 \right)=\frac{n(n+1)(2n+1)}{2}$

$\displaystyle\sum_{k=0}^n\left(k^2 \right)=\frac{n(n+1)(2n+1)}{6}$

We may continue this process, to find further power summations.

Method 2: A recursion approach...

Suppose we want to find:

$\displaystyle S_n=\sum_{k=0}^n\left(k^3 \right)$

We may use the inhomogeneous recursion to state:

$\displaystyle S_n=S_{n-1}+n^3$

Now, we may use symbolic differencing to ultimately derive a homogeneous recursion.

We begin by replacing n with n + 1:

$\displaystyle S_{n+1}=S_{n}+(n+1)^3$

Subtracting the former from the latter, there results:

$\displaystyle S_{n+1}=2S_{n}-S_{n-1}+3n^2+3n+1$

$\displaystyle S_{n+2}=2S_{n+1}-S_{n}+3(n+1)^2+3(n+1)+1$

Subtracting again:

$\displaystyle S_{n+2}=3S_{n+1}-3S_{n}+S_{n-1}+6n+6$

$\displaystyle S_{n+3}=3S_{n+2}-3S_{n+1}+S_{n}+6(n+1)+6$

Subtracting again:

$\displaystyle S_{n+3}=4S_{n+2}-6S_{n+1}+4S_{n}-S_{n-1}+6$

$\displaystyle S_{n+4}=4S_{n+3}-6S_{n+2}+4S_{n+1}-S_{n}+6$

Subtracting again:

$\displaystyle S_{n+4}=5S_{n+3}-10S_{n+2}+10S_{n+1}-5S_{n}+S_{n-1}$

Now we have a homogeneous recursion whose associated characteristic equation is:

$\displaystyle (r-1)^5=0$

Since we have the root $\displaystyle r=1$ of multiplicity 5, we know the closed form for the sum will take the form:

$\displaystyle S_n=k_0+k_1n+k_2n^2+k_3n^3+k_4n^4$

We may use known initial values to determine the constants $\displaystyle k_i$.

$\displaystyle S_0=k_0=0$

This means, we are left with the 4X4 system:

$\displaystyle k_1+k_2+k_3+k_4=1$

$\displaystyle 2k_1+4k_2+8k_3+16k_4=9$

$\displaystyle 3k_1+9k_2+27k_3+81k_4=36$

$\displaystyle 4k_1+16k_2+64k_3+256k_4=100$

Did you notice we get the squares of successive triangular numbers? Anyway, solving this system, we find:

$\displaystyle k_1=0,k_2=\frac{1}{4},k_3=\frac{1}{2},k_4=\frac{1}{4}$

And so, we have:

$\displaystyle S_n=\frac{1}{4}n^2+\frac{1}{2}n^3+\frac{1}{4}n^4= \frac{n^4+2n^3+n^2}{4}=$

$\displaystyle\frac{n^2(n+1)^2}{4}=\left( \frac{n(n+1)}{2} \right)^2$

 

[melese]

a nice combinatorial proof

View attachment 348To each yellow circle we can associate a pair of green circles in the way suggested by the drawing. This shows a bijection between (and hence the same number of) all the yellow circles and all the pairs of green circles.

Here, there are $1+2+3+4+5+6+7+8$ yellow circles, and the number of green-circle pairs is $\binom{9}{2}$; so $1+2+3+4+5+6+7+8=\binom{9}{2}$.

(I saw this 'proof without words' in a lecture by Gil Kalai)

 

[HallsofIvy]

Mark on Yahoo answers asks:
Allegedly his method was something like:

$(1+100)+(2+99)+ ... +(99+2)+(100+1)=2(1+2+...+100)$

But the left hand side is $101\times 100$, so $1+2+..100=101\times 100/2$

(Like Marlow's Dr Faustus he could sum them forwards and backwards - but had no need of anagramatisation)

CB

The way I heard it was that he noted, as you have, that 1+ 100= 101, 2+ 99= 101, etc. until 50+ 51= 101 so there were 50 sums, each totalling 101: 50(101)= 5050.