Home Discussion Topics Dictionary Almanac

Signup Login

Summation

Discussion

Ask a question about 'Summation'

Start a new discussion about 'Summation'

Answer questions from other users

Full Discussion Forum

Encyclopedia

Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum

Prefix sum

In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....

, or running total

Running total

A running total is the summation of a sequence of numbers which is updated each time a new number is added to the sequence, simply by adding the value of the new number to the running total....

of the summation. The numbers to be summed may be integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s, rational number

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

s, real number

Real number

In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s, or complex number

Complex number

A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s. Besides numbers, other types of values can be added as well: vectors

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

, matrices

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

, polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

s and, in general, elements of any additive group

Additive group

An additive group may refer to:*an abelian group, when it is written using the symbol + for its binary operation*a group scheme representing the underlying-additive-group functor...

(or even monoid

Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...

). For finite sequences of such elements, summation always produces a well-defined sum (possibly by virtue of the convention for empty sum

Empty sum

In mathematics, an empty sum, or nullary sum, is a summation involving no terms at all. The value of any empty sum of numbers is conventionally taken to be zero...

s).

Summation of an infinite sequence of values is not always possible, and when a value can be given for an infinite summation, this involves more than just the addition operation, namely also the notion of a limit

Limit (mathematics)

In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...

. Such infinite summations are known as series

Series (mathematics)

A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....

. Another notion involving limits of finite sums is integration

Integral

Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

. The term summation has a special meaning related to extrapolation

Extrapolation

In mathematics, extrapolation is the process of constructing new data points. It is similar to the process of interpolation, which constructs new points between known points, but the results of extrapolations are often less meaningful, and are subject to greater uncertainty. It may also mean...

in the context of divergent series

Divergent series

In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a limit....

.

The summation of the sequence [1, 2, 4, 2] is an expression

Expression (mathematics)

In mathematics, an expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Symbols can designate numbers , variables, operations, functions, and other mathematical symbols, as well as punctuation, symbols of grouping, and other syntactic...

whose value is the sum of each of the members of the sequence. In the example, = 9. Since addition is associative the value does not depend on how the additions are grouped, for instance and both have the value 9; therefore, parentheses are usually omitted in repeated additions. Addition is also commutative, so permuting

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

the terms of a finite sequence does not change its sum (for infinite summations this property may fail; see absolute convergence

Absolute convergence

In mathematics, a series of numbers is said to converge absolutely if the sum of the absolute value of the summand or integrand is finite...

for conditions under which it still holds).

There is no special notation for the summation of such explicit sequences, as the corresponding repeated addition expression will do. There is only a slight difficulty if the sequence has less than two elements: the summation of a sequence of one term involves no plus sign (it is indistinguishable from the term itself) and the summation of the empty sequence cannot even be written down (but one can write its value "0" in its place). If, however, the terms of the sequence are given by a regular pattern, possibly of variable length, then a summation operator may be useful or even essential. For the summation of the sequence of consecutive integers from 1 to 100 one could use an addition expression involving an ellipsis

Ellipsis

Ellipsis is a series of marks that usually indicate an intentional omission of a word, sentence or whole section from the original text being quoted. An ellipsis can also be used to indicate an unfinished thought or, at the end of a sentence, a trailing off into silence...

to indicate the missing terms: . In this case the reader easily guesses the pattern; however, for more complicated patterns, one needs to be precise about the rule used to find successive terms, which can be achieved by using the summation operator "Σ". Using this notation the above summation is written as:

The value of this summation is 5050. It can be found without performing 99 additions, since it can be shown (for instance by mathematical induction

Mathematical induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

) that

for all natural numbers n. More generally, formulas exist for many summations of terms following a regular pattern.

The term "indefinite summation" refers to the search for an inverse image of a given infinite sequence s of values for the forward difference operator, in other words for a sequence, called antidifference of s, whose finite difference

Finite difference

A finite difference is a mathematical expression of the form f − f. If a finite difference is divided by b − a, one gets a difference quotient...

s are given by s. By contrast, summation as discussed in this article is called "definite summation".

Capital-sigma notation

Mathematical notation uses a symbol that compactly represents summation of many similar terms: the summation symbol ∑ (U+2211), an enlarged form of the upright capital Greek letter Sigma. This is defined thus:

The subscript gives the symbol for an index variable

Index (mathematics)

The word index is used in variety of senses in mathematics.- General :* In perhaps the most frequent sense, an index is a number or other symbol that indicates the location of a variable in a list or array of numbers or other mathematical objects. This type of index is usually written as a...

, i. Here, i represents the index of summation; m is the lower bound of summation, and n is the upper bound of summation. Here i = m under the summation symbol means that the index i starts out equal to m. Successive values of i are found by adding 1 to the previous value of i, stopping when i = n. An example:

Informal writing sometimes omits the definition of the index and bounds of summation when these are clear from context, as in

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:

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

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

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

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

is the same as

A similar notation is applied when it comes to denoting the product of a sequence, which is similar to its summation, but which uses the multiplication operation instead of addition (and gives 1 for an empty sequence instead of 0). The same basic structure is used, with ∏, an enlarged form of the Greek capital letter Pi

Pi (letter)

Pi is the sixteenth letter of the Greek alphabet, representing . In the system of Greek numerals it has a value of 80. Letters that arose from pi include Cyrillic Pe , Coptic pi , and Gothic pairthra .The upper-case letter Π is used as a symbol for:...

, replacing the ∑.

Special cases

It is possible to sum fewer than 2 numbers:

If the summation has one summand x, then the evaluated sum is x.
If the summation has no summands, then the evaluated sum is zero
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...

, because zero is the identity
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

for addition. This is known as the empty sum
Empty sum
In mathematics, an empty sum, or nullary sum, is a summation involving no terms at all. The value of any empty sum of numbers is conventionally taken to be zero...

.

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, then there is none.

Formal Definition

If the iterated function

Iterated function

In mathematics, an iterated function is a function which is composed with itself, possibly ad infinitum, in a process called iteration. In this process, starting from some initial value, the result of applying a given function is fed again in the function as input, and this process is repeated...

notation is defined e.g.

and is considered a more primitive notation then summation can be defined in terms of iterated functions as:

Where the curly braces define a 2-tuple

Tuple

In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

and the right arrow is a function definition taking a 2-tuple to 2-tuple. The function is applied b-a+1 times on the tuple {a,0}.

Measure theory notation

In the notation of measure and integration

Integral

Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

theory, a sum can be expressed as a definite integral,

where is the subset of the integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s from to , and where is the counting measure

Counting measure

In mathematics, the counting measure is an intuitive way to put a measure on any set: the "size" of a subset is taken to be the number of elements in the subset, if the subset is finite, and ∞ if the subset is infinite....

Fundamental theorem of discrete calculus

Indefinite sums can be used to calculate definite sums with the formula:

Approximation by definite integrals

Many such approximations can be obtained by the following connection between sums and integral

Integral

Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

s, which holds for any:

increasing

Monotonic function

In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

function f:

decreasing

Monotonic function

In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

function f:

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

For summations in which the summand is given (or can be interpolated) by an integrable

Riemann integral

In the branch of mathematics known as real analysis, the Riemann integral, created by Bernhard Riemann, was the first rigorous definition of the integral of a function on an interval. The Riemann integral is unsuitable for many theoretical purposes...

function of the index, the summation can be interpreted as a Riemann sum

Riemann sum

In mathematics, a Riemann sum is a method for approximating the total area underneath a curve on a graph, otherwise known as an integral. It mayalso be used to define the integration operation. The method was named after German mathematician Bernhard Riemann....

occurring in the definition of the corresponding definite integral. One can therefore expect that for instance

since the right hand side is by definition the limit for

of the left hand side. However for a given summation n is fixed, and little can be said about the error in the above approximation without additional assumptions about f: it is clear that for wildly oscillating functions the Riemann sum can be arbitrarily far from the Riemann integral.

Identities

The formulas below involve finite sums; for infinite summations see list of mathematical series

General manipulations

, where C is a constant

Some summations of polynomial expressions

(See Harmonic number)

(see arithmetic series)

(Special case of the arithmetic series)

where

denotes a Bernoulli number

Bernoulli number

In mathematics, the Bernoulli numbers Bn are a sequence of rational numbers with deep connections to number theory. They are closely related to the values of the Riemann zeta function at negative integers....

The following formulas are manipulations of

generalized to begin a series at any natural number value (i.e.,

Some summations involving exponential terms

In the summations below x is a constant not equal to 1

(geometric series starting at 1)

(special case when x = 2)

(special case when x = 1/2)

Some summations involving binomial coefficients

There exist enormously many summation identities involving binomial coefficients (a whole chapter of Concrete Mathematics

Concrete Mathematics

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, is a mathematical textbook that is widely used in computer-science departments. It provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms...

is devoted to just the basic techniques). Some of the most basic ones are the following.

, the binomial theorem

Binomial theorem

In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with , and the coefficient a of...

Growth rates

The following are useful approximation

Approximation

An approximation is a representation of something that is not exact, but still close enough to be useful. Although approximation is most often applied to numbers, it is also frequently applied to such things as mathematical functions, shapes, and physical laws.Approximations may be used because...

s (using theta notation

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...