Sum

A sum is the result of an Addition. For example, adding 1, 2, 3, and 4 gives the sum 10, written

$$1+2+3+4=10.$$ (1)

The numbers being summed are called Addends, or sometimes Summands. The summation operation can also be indicated using a capital sigma with upper and lower limits written above and below, and the index indicated below. For example, the above sum could be written

$$\sum_{k=1}^4 k=10.$$ (2)

A simple graphical proof of the sum $\sum_{k=1}^n k=n(n+1)/2$ can also be given. Construct a sequence of stacks of boxes, each 1 unit across and $k$ units high, where $k=1$, 2, ..., $n$. Now add a rotated copy on top, as in the above figure. Note that the resulting figure has Width $n$ and Height $n+1$, and so has Area $n(n+1)$. The desired sum is half this, so the Area of the boxes in the sum is $n(n+1)/2$. Since the boxes are of unit width, this is also the value of the sum.

The sum can also be computed using the first Euler-Maclaurin Integration Formula

$$\sum_{k=1}^n f(k) = \int_1^n f(x)\,dx+{\textstyle{1\over 2}}... ...\over 2}}f(n)+{\textstyle{1\over 2!}} B_2 [f'(n)-f'(1)]+\ldots$$ (3)

with $f(k)=k$. Then

$$\sum_{k=1}^n k = \int_1^n x\,dx +{\textstyle{1\over 2}}\cdot 1+{\textstyle{1\over 2}}\cdot n+{\textstyle{1\over 6}}(1-1)+\ldots$$

$$= {\textstyle{1\over 2}}(n^2-1)-{\textstyle{1\over 2}}+h+{\textstyle{1\over 2}}n = {\textstyle{1\over 2}}n(n+1).$$ (4)

The general finite sum of integral Powers can be given by the expression

$$\sum_{k=1}^n k^p = {(B+n+1)^{[p+1]}-B^{[p+1]}\over p+1},$$ (5)

where the Notation $B^{[k]}$ means the quantity in question is raised to the appropriate Power $k$ and all terms of the form $B^m$ are replaced with the corresponding Bernoulli Numbers $B_m$. It is also true that the Coefficients of the terms in such an expansion sum to 1, as stated by Bernoulli without proof (Boyer 1943).

An analytic solution for a sum of Powers of integers is

$$\sum_{k=1}^n k^p = \zeta(-p)-\zeta(-p,1+n),$$ (6)

where $\zeta(z)$ is the Riemann Zeta Function and $\zeta(z;a)$ is the Hurwitz Zeta Function. For the special case of $p$ a Positive integer, Faulhaber's Formula gives the Sum explicitly as

$$\sum_{k=1}^n k^p = {1\over p+1}\sum_{k=1}^{p+1} (-1)^{\delta_{kp}} {p+1\choose k}B_{p+1-k} n^k,$$ (7)

where $\delta_{kp}$ is the Kronecker Delta, ${n\choose k}$ is a Binomial Coefficient, and $B_k$ is a Bernoulli Number. Written explicitly in terms of a sum of Powers,

$$\sum_{k=1}^n k^p = {B_k p!\over k!(p-k+1)!} n^{p-k+1}.$$ (8)

Computing the sums for $p=1$, ..., 10 gives

$$\sum_{k=1}^n k = {\textstyle{1\over 2}}(n^2+n)$$ (9)

$$\sum_{k=1}^n k^2 = {\textstyle{1\over 6}}(2n^3+3n^2+n)$$ (10)

$$\sum_{k=1}^n k^3 = {\textstyle{1\over 4}}(n^4+2n^3+n^2)$$ (11)

$$\sum_{k=1}^n k^4 = {\textstyle{1\over 30}}(6n^5+15n^4+10n^3-n)$$ (12)

$$\sum_{k=1}^n k^5 = {\textstyle{1\over 12}}(2n^6+6n^5+5n^4-n^2)$$ (13)

$$\sum_{k=1}^n k^6 = {\textstyle{1\over 42}}(6n^7+21n^6+21n^5-7n^3+n)$$ (14)

$$\sum_{k=1}^n k^7 = {\textstyle{1\over 24}}(3n^8+12n^7+14n^6-7n^4+2n^2)$$ (15)

$$\sum_{k=1}^n k^8 = {\textstyle{1\over 90}}(10n^9+45n^8+60n^7-42n^5+20n^3-3n)$$ (16)

$$\sum_{k=1}^n k^9 = {\textstyle{1\over 20}}(2n^{10}+10n^9+15n^8-14n^6+10n^4-3n^2)$$ (17)

$$\sum_{k=1}^n k^{10} = {\textstyle{1\over 66}}(6n^{11}+33n^{10}+55n^9-66n^7+66n^5-33n^3+5n).$$ (18)

Factoring the above equations results in

$\sum_{k=1}^n k = {\textstyle{1\over 2}}n(n+1)$	(19)
$\sum_{k=1}^n k^2 = {\textstyle{1\over 6}}n(n+1)(2n+1)$	(20)
$\sum_{k=1}^n k^3 = {\textstyle{1\over 4}}n^2(n+1)^2$	(21)
$\sum_{k=1}^n k^4 = {\textstyle{1\over 30}}n(n+1)(2n+1)(3n^2+3n-1)$	(22)
$\sum_{k=1}^n k^5 = {\textstyle{1\over 12}}n^2(n+1)^2(2n^2+2n-1)$	(23)
$\sum_{k=1}^n k^6 = {\textstyle{1\over 42}}n(n+1)(2n+1)(3n^4+6n^3-3n+1)$	(24)
$\sum_{k=1}^n k^7 = {\textstyle{1\over 24}}n^2(n+1)^2(3n^4+6n^3-n^2-4n+2)$	(25)
$\sum_{k=1}^n k^8 = {\textstyle{1\over 90}}n(n+1)(2n+1)(5n^6+15n^5+5n^4-15n^3-n^2+9n-3)$	(26)
$\sum_{k=1}^n k^9 = {\textstyle{1\over 20}}n^2(n+1)^2(n^2+n-1)(2n^4+4n^3-n^2-3n+3)$	(27)
$\sum_{k=1}^n k^{10} = {\textstyle{1\over 66}}n(n+1)(2n+1)(n^2+n-1)$
$\times(3n^6+9n^5+2n^4-11n^3+3n^2+10n-5).\quad$	(28)

From the above, note the interesting identity

$$\sum_{k=1}^n k^3 = \left({\,\sum_{k=1}^n k}\right)^2.$$ (29)

Sums of the following type can also be done analytically.

$${\left({\,\sum_{k=0}^\infty x^k}\right)}^2 = \sum_{n=0}^\infty \left({\,\sum_{k=0}^n 1}\right)x^n = \sum_{n=0}^\infty (n+1)x^n$$ (30)

$${\left({\,\sum_{k=0}^\infty} x^k\right)}^3 = \sum_{n=0}^\infty\left({\,\sum_{k=0}^n k}\right)x^n$$

$$= {1\over 2}\sum_{n=0}^\infty (n+1)(n+2)x^n$$ (31)

$$\left({\,\sum_{k=0}^\infty} x^k\right)^4 = \sum_{n=0}^\infty \left[{\,\sum_{k=0}^n {\textstyle{1\over 2}}(k+1)(k+2)}\right]x^n$$

$$= {1\over 2} \sum_{n=0}^\infty \left({\,\sum_{k=0}^n {k^2+3k+2}}\right)x^n$$

$$= {1\over 2} \sum_{n=0}^\infty [{\textstyle{1\over 6}} n(n+1)(2n+1)+3 {\textstyle{1\over 2}}n(n+1)+2(n+1)]x^n$$

$$= {1\over 12} \sum_{n=0}^\infty (n+1)[n(2n+1)+9n+12]x^n$$

$$= {1\over 12} \sum_{n=0}^\infty (n+1)(2n^2+10n+12)x^n$$

$$= {1\over 6} \sum_{n=0}^\infty (n+1)(n+2)(n+3)x^n.$$ (32)

By Induction, the sum for an arbitrary Power $p$ is

$${\left({\,\sum_{k=0}^\infty} x^k\right)}^p = {1\over (p-1)!} \sum_{n=0}^\infty {(n+p-1)!\over n!} x^n.$$ (33)

Other analytic sums include

$${\left({\,\sum_{k=0}^n} x^k\right)}^2 = {1\over (p-1)!} \sum... ...0}^{2n} {(n-\vert n-k\vert+p-1)!\over (n-\vert n-k\vert)!} x^k$$ (34)

$$\left({\,\sum_{n=0}^\infty a_nx^n}\right)^2 = \sum_{n=0}^\in... ...op\scriptstyle i+j=n}\atop\scriptstyle i<j}^\infty a_ia_j x^n.$$ (35)

$$\sum xy = x_1y_1+x_1y_2+\ldots+x_2y_1+x_2y_2+\ldots$$

$$= (x_1+x_2+\ldots)y_1+(x_1+x_2+\ldots)y_2$$

$$= \left({\sum x}\right)(y_1+y_2+\ldots) = \sum x\sum y,$$ (36)

so

$$\sum_{i=1}^m \sum_{j=1}^n x_iy_j = \left({\,\sum_{i=1}^m x_i}\right)\left({\,\sum_{j=1}^n y_j}\right).$$ (37)

$$\sum_{j=0}^n jx^j = {nx^{n+2}-(n+1)x^{n+1}+x\over (x-1)^2}$$ (38)

$$\sum_{j=1}^n {{x_j}^r\over \prod_{\scriptstyle k=1\atop\scri... ...<n-1$\cr 1 & for $r=n-1$\cr \sum_{j=1}^n x_j & for $r=n$\cr}$$ (39)

$$\sum_{k=1}^n {\prod_{\scriptstyle r=1\atop\scriptstyle r\not... ...\prod_{\scriptstyle r=1\atop\scriptstyle r\not=k}^n (k-r)} = 1$$ (40)

$$(n+1)\sum_{m=1}^n m^k =\sum_{m=1}^n \left[{m^{k+1}+\sum_{p=1}^n\left({\sum_{m=1}^p m^k}\right)}\right].$$ (41)

To minimize the sum of a set of squares of numbers $\{x_i\}$ about a given number $x_0$

$$S\equiv \sum_i (x_i-x_0)^2=\sum_i {x_i}^2-2x_0\sum x_i+N{x_0}^2,$$ (42)

take the Derivative.

$${d\over dx_0} S =-2\sum_i x_i+2Nx_0=0.$$ (43)

Solving for $x_0$ gives

$$x_0\equiv \bar x={1\over N}\sum_i x_i,$$ (44)

so $S$ is maximized when $x_0$ is set to the Mean.

See also Arithmetic Series, Bernoulli Number, Clark's Triangle, Convergence Improvement, Dedekind Sum, Double Sum, Euler Sum, Factorial Sum, Faulhaber's Formula, Gabriel's Staircase, Gaussian Sum, Geometric Series, Gosper's Method, Hurwitz Zeta Function, Infinite Product, Kloosterman's Sum, Legendre Sum, Lerch Transcendent, Pascal's Triangle, Product, Ramanujan's Sum, Riemann Zeta Function, Whitney Sum

References

Boyer, C. B. ``Pascal's Formula for the Sums of the Powers of the Integers.'' Scripta Math. 9, 237-244, 1943.

Courant, R. and Robbins, H. ``The Sum of the First $n$ Squares.'' §1.4 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 14-15, 1996.

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A. K. Peters, 1996.