Sum of integers


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



Sum of cubes



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

Leave a Reply

Your email address will not be published. Required fields are marked *