Summation

From Exampleproblems

(Redirected from Sum)

Summation is the addition of a set of numbers; the result is their sum. The "numbers" to be summed may be natural numbers, complex numbers, matrices, or still more complicated objects. An infinite sum is a subtle procedure known as a series.

1 Notation
- 1.1 Computerized notation
- 1.2 Special cases
2 Approximation by definite integrals
3 Identities
4 Growth rates
5 See also
6 External links

Notation

The sum of 1, 2, and 4 is 1 + 2 + 4 = 7. Since addition is associative, it does not matter whether we interpret "1 + 2 + 4" as (1 + 2) + 4 or as 1 + (2 + 4); the result is the same, so parentheses are usually omitted in a sum. Addition is also commutative, so the order in which the numbers written does not affect its sum.

If a sum has too many terms to write them all out individually, the sum may be written with an ellipsis to mark out the missing terms. Thus, the sum of all the natural numbers from 1 to 100 is 1 + 2 + … + 99 + 100 = 5050.

Sums can be represented by the summation symbol, a capital Sigma. This is defined as:

$\sum_{i=m}^n x_i = x_m + x_{m+1} + x_{m+2} +\cdots+ x_{n-1} + x_n.$

The subscript gives the symbol for a dummy variable, i. Here, i represents the index of summation; m is the lower bound of summation, and n is the upper bound of summation. So, for example:

$\sum_{x=2}^6 x^2 = 2^2+3^2+4^2+5^2+6^2 = 90.$

One often sees generalizations of this notation in which an arbitrary logical condition is supplied, and the sum is intended to be taken over all values satisfying the condition. For example:

$\sum_{0\le x< 100} f(x)$

is the sum of f(x) over all (integer) x in the specified range,

$\sum_{x\in S} f(x)$

is the sum of f(x) over all integers x in the set S, and

$\sum_{d|n}\;\mu(d)$

is the sum of μ(d) over all integers d dividing n.

There are also ways to generalize the use of many sigma signs. For example,

$\sum_{\ell,\ell'}$

is the same as

$\sum_\ell\sum_{\ell'}.$

Computerized notation

Summations can also be represented in a programming language.

$\sum_{i=m}^{n} x_{i}$

is computed by the following JavaScript program:

 sum=0;
 for(i=m; i<=n; i++)
   sum += x[i];

Special cases

It's possible to add fewer than 2 numbers:

If you add the single term x, then the sum is x.
If you add zero terms, then the sum is zero, because zero is the identity for addition. This is known as the empty sum.

These degenerate cases are usually only used when the summation notation gives a degenerate result in a special case. For example, if m = n in the definition above, then there is only one term in the sum; if m = n + 1, then there is none.

Approximation by definite integrals

Many such approximations can be obtained by the following connection between sums and integrals, which holds for any increasing function f:

$\int_{s=a-1}^{b} f(s)\, ds \le \sum_{i=a}^{b} f(i) \le \int_{s=a}^{b+1} f(s)\, ds.$

For more general approximations, see the Euler-Maclaurin formula.

For functions that are integrable on the interval $[a, b]$ , the Riemann sum can be used as an approximation of the definite integral. For example, the following formula is the left Riemann sum with equal partitioning of the interval:

$\frac{b-a}{n}\sum_{i=0}^{n-1} f\left(a+i\frac{b-a}n\right)\approx \int_a^b f(x)\,dx.$

The accuracy of such an approximation increases with the number n of subintervals.

Identities

The following are useful identities:

$\sum_{i=1}^n x = nx$
$\sum_{i=m}^n i = \frac{(n-m+1)(n+m)}{2}$
$\sum_{i=0}^n i = \frac {n(n+1)}{2}$ (see arithmetic series)
$\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6}$
$\sum_{i=0}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2$
$\sum_{i=0}^n i^p = \frac{(n+1)^{p+1}}{p+1} + \sum_{k=1}^p\frac{B_k}{p-k+1}{p\choose k}(n+1)^{p-k+1}$

where

B k

is the kth Bernoulli number.

$\sum_{i=m}^n x^i = \frac{x^{n+1}-x^{m}}{x-1}$ (see geometric series)
$\sum_{i=0}^n x^i = \frac{1-x^{n+1}}{1-x}$ (special case of the above where m = 0)
$\sum_{i=0}^n {n \choose i} = 2^n$ (see binomial coefficient)
$\sum_{i=0}^{n-1} {i \choose k} = {n \choose k+1}$
$\left(\sum_i a_i\right)\left(\sum_j b_j\right) = \sum_i\sum_j a_ib_j$
$\left(\sum_i a_i\right)^2 = 2\sum_i\sum_{j<i} a_ia_j + \sum_i a_i^2$

Growth rates

The following are useful approximations (using theta notation):

$\sum_{i=1}^n i^c = \Theta(n^{c+1})$ for real c greater than -1
$\sum_{i=1}^n \frac{1}{i} = \Theta(\log n)$
$\sum_{i=1}^n c^i = \Theta(c^n)$ for real c greater than 1
$\sum_{i=1}^n \log(i)^c = \Theta(n \cdot \log(n)^{c})$ for nonnegative real c
$\sum_{i=1}^n \log(i)^c \cdot i^d = \Theta(n^{d+1} \cdot \log(n)^{c})$ for nonnegative real c, d
$\sum_{i=1}^n \log(i)^c \cdot i^d \cdot b^i = \Theta (n^d \cdot \log(n)^c \cdot b^n)$ for nonnegative real b > 1, c, d