Sums | adamponting.com

Sum of integers

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

$\frac{n(n+1)}{2}$ is the number of terms $n$ times the average of the first term and the last, $\frac{1+n}{2}$ .
intsum 20
sumPicture 1
The picture shows that twice the sum, $2S=n^2+n$ , so $S=\fr{2}(n^2+n)=\frac{n(n+1)}{2}$ .

General arithmetic progression
The sum of $n$ terms of an arithmetic progression $a,a+d,a+2d\dots$ is the average of the first and last terms, times the number of terms.
$S=a+(a+d)+(a+2d)+\dots+(a+(n-1)d)=\sum\limits_{k=0}^{n-1} (a+kd)=n(\frac{a+a+(n-1)d}{2})$
sumpic1
This diagram shows that $S$ is $1/2$ the size of a rectangle of height $n$ and width $(a+(n-1)d)+a$ .

Sum of squares

$\boxed{1^2+2^2+3^2+4^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}=\frac{n(n+\fr{2})(n+1)}{3}}$

sumsq13
sumsq15

Sum of cubes

sumcub30

cubesum16

For the sum of higher powers, see Jacob Bernoulli’s power sum problem

Manipulating sums

$\begin{align*} &\sum ca_k &=&&c\sum a_k&&\text{ (distributive law)} &\\ &\sum (a_k+b_k)&=&&\sum a_k+\sum b_k&&\text{ (associative law)}& \\ &\sum_{k\text{ in }K}a_k&=&&\sum_{p(k)\text{ in }K} a_{p(k)}&&\text{ (commutative law)}& \end{align*}$

where $p(k)$ is a permutation of the elements of $K$ – i.e. the elements can be taken in any order.

Gauss’ boyhood trick of finding $1+2+3+\dots+100$ can be seen as an application of these 3 laws.
To find the general sum of an arithmetic progression

$S=\sum\limits_{0\les k\les n} (a+bk),$

We can replace $k$ by $n-k$ (commutative law):

$S=\sum\limits_{0\les n-k\les n} \big(a+b(n-k)\big)=\sum\limits_{0\les k\les n} (a+bn-bk)$

Add these 2 together. (associative law)

$2S=\sum\limits_{0\les k\les n} \big((a+bk)+(a+bn-bk)\big) =\sum\limits_{0\les k\les n} (2a+bn)$

Take the constant outside the sum. (distributive law)

$2S=(2a+bn)\sum\limits_{0\les k\les n}1=(2a+bn)(n+1)$

Divide this by $2$ to get:

$S=\sum\limits_{0\les k\les n} (a+bk)=(a+\fr{2}bn)(n+1)$

– the average of the first and last terms, $\fr{2}(a+(a+bn))$ , times the number of terms.

Example of finding a sum

I wanted to make a video that starts in very slow-motion, and gradually accelerates up to 30 (different) frames a second. Maybe start with 2 images each 1/2 second long (15 frames each), then 3 images 14 frames long, 4×13, 5×12 etc until 14×3, 15 2 frames long, then return to regular 1 image per 1/30 second. How long would this take? It would take:
$15\times2+14\times3+13\times4+12\times5+...+3\times14+2\times15$ frames/30ths of a second.
If we represent the numbers rising $2,3,4\dots$ (the number of images shown for a given number of frames, e.g. initially, 2 images last for 15 frames each) by $f$ , then the other $15,14,13\dots$ is $17-f$ , and the sum is:

$\begin{align*} \sum_{2\les f \les 15}(17-f)f &= \displaystyle\sum_{2\les f \les 15}17f-\sum_{2\les f \les 15}f^2 \\ &= 17\sum_{2\les f \les 15}f-\sum_{2\les f \les 15}f^2 \end{align*}$

These two are the above 2 series for $n$ and $n^2$ , with only slight modification:

$\sum_{2\les f \les 15}f=(1+2+3+4+\dots+15)-1$

$\sum_{2\les f \les 15}f^2=(1^2+2^2+3^2+4^2+\dots+15^2)-1$

So the sum can be written as:

$\displaystyle17(\frac{n(n+1)}{2}-1)-\big(\frac{n(n+1)(2n+1)}{6}-1\big)$ with $n=15$ , i.e.

$\begin{align*} \frac{17\times15\times16}{2}-17-\frac{15\times16\times31}{6}+1&=15\times16\times(\frac{17}{2}-\frac{31}{6})-17+1 \\ &=15\times16\times(\frac{51-31}{6})-16\\ &=\frac{15\times16\times20}{6}-16 \\ &=800-16 \\ &=784 \text{ frames, or 30ths of a second.} \\ &\sim26 \text{ seconds.} \end{align*}$

Another way using Newton’s formula:

$\boxed{f(x)=f(0)+\Delta f(0)x+\Delta ^2f(0)\frac{\fp{x}{2}}{2!}+\Delta ^3f(0)\frac{\fp{x}{3}}{3!}+\dots}$

where $\Delta f(0)=f(1)-f(0),\quad \Delta ^2f(0)=\Delta f(1)-\Delta f(0),\quadd\text{ etc.}$
and the falling power $\fp{x}{n}=x(x-1)(x-2)\dots(x-n+1)$

The sought value is a term in the series:
$2\times15,\quad 2\times15+3\times14,\quad 2\times15+3\times14+4\times13,\dots$
We need the term ending in $\dots\times2$ , evidently the 14th term.
Add a first term $0$ for $f(0)=0$ , and the values in this case are:

$\begin{align*} &x &&f(x) && \Delta f(x) && \Delta^2f(x) && \Delta^3f(x)&&\Delta^4f(x)& \\ &0 &&0 &&30 &&12 &&-2 && 0& \\ &1 &&30 &&42 &&10 && -2 && &\\ &2 &&72 &&52 && 8 && && &\\ &3 &&124&&60 && && && & \end{align*}$

Newton’s formula gives:

$\begin{align*} f(x)&=0+30\fp{x}{1}+\frac{12\fp{x}{2}}{2!}-\frac{2\fp{x}{3}}{3!} \\ &=30x+6x(x-1)-\fr{3}x(x-1)(x-2) \\ &=30x+6x^2-6x-\fr{3}(x^3-3x^2+2x) \\ &=\frac{90x+18x^2-18x-x^3+3x^2-2x}{3} \\ &=\frac{-x^3+21x^2+70x}{3} \\ &=\frac{x}{3}\Big(x(21-x)+70\Big) \\[8pt] f(14)&=\frac{14}{3}( 14 \times 7+70)=784 \end{align*}$

Well, what’s the general formula, for starting with a number $f$ of images each shown for $N$ 30ths of a second? i.e. the sum is then:
$N\times f+(N-1)(f+1)+(N-2)(f+2)+\dots+2\times (N+f-2)$
If one number from each of these pairs is $j$ , the other will be equal to $N+f-j$ . (Like both numbers always added to 17 in the last example.)
So this time we have

$\begin{align*} \sum_{2\les j\les N} j(N+f-j)&= \sum_{2\les j\les N} j(N+f)-j^2 \\ &= (N+f)\sum_{2\les j\les N} j-\sum_{2\les j\les N} j^2 \\ &=(N+f)\big(\frac{N(N+1)}{2}-1\big)-(\frac{N(N+1)(2N+1)}{6}-1) \\ &=\frac{1}{2}N(N+1)(N+f)-(N+f)-N(N+1)\frac{2N+1}{6}+1 \\ &=N(N+1)(\frac{N+f}{2}-\frac{2N+1}{6})-(N+f)+1 \\ &=\big(\frac{N(N+1)}{6}-1\big)(N+3f-1)+2f \end{align*}$

And just to check this formula, plugging in $N=15$ and $f=2$ :

$=(\frac{15\times 16}{6}-1)\times 20 +4=39\times 20+4=784$ frames.

Knuth et al – Concrete Mathematics

Sum of integers

Sum of squares

Sum of cubes

Leave a Reply Cancel reply