Summation
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
, or running total
of the summation. The numbers to be summed may be integer
s, rational number
s, real number
s, or complex number
s. Besides numbers, other types of values can be added as well: vectors
, matrices
, polynomial
s and, in general, elements of any additive group
(or even monoid
). For finite sequences of such elements, summation always produces a well-defined sum (possibly by virtue of the convention for empty sum
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
. Such infinite summations are known as series
. Another notion involving limits of finite sums is integration
. The term summation has a special meaning related to extrapolation
in the context of divergent series
.
The summation of the sequence[ 1, 2, 4, 2] is an expression
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
the terms of a finite sequence does not change its sum (for infinite summations this property may fail; see absolute convergence
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
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
) 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
s are given by s. By contrast, summation as discussed in this article is called "definite summation".
The subscript gives the symbol for an index variable
, 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
, replacing the ∑.
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.
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
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}.
theory, a sum can be expressed as a definite integral,
where is the subset of the integer
s from to , and where is the counting measure
.
s, which holds for any:
increasing
function f:
decreasing
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
function of the index, the summation can be interpreted as a Riemann sum
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.
The following formulas are manipulations of
generalized to begin a series at any natural number value (i.e., 
):
is devoted to just the basic techniques). Some of the most basic ones are the following.
s (using theta notation
):
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
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 zero0 (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 identityIdentity elementIn 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 sumEmpty sumIn 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 functionIterated 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 integrationIntegral
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 integralIntegral
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 seriesGeneral 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 numberBernoulli numberIn 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 MathematicsConcrete 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 theoremBinomial theoremIn 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 approximationApproximation
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...
):
-
for real c greater than −1 -
(See Harmonic number) -
for real c greater than 1 -
for non-negative real c -
for non-negative real c, d -
for non-negative real b > 1, c, d
See also
- Einstein notationEinstein notationIn mathematics, especially in applications of linear algebra to physics, the Einstein notation or Einstein summation convention is a notational convention useful when dealing with coordinate formulae...
- ChecksumChecksumA checksum or hash sum is a fixed-size datum computed from an arbitrary block of digital data for the purpose of detecting accidental errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and...
- Product (mathematics)Product (mathematics)In mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. The order in which real or complex numbers are multiplied has no bearing on the product; this is known as the commutative law of multiplication...
- Kahan summation algorithmKahan summation algorithmIn numerical analysis, the Kahan summation algorithm significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious approach...
- Iterated binary operationIterated binary operationIn mathematics, an iterated binary operation is an extension of a binary operation on a set S to a function on finite sequences of elements of S through repeated application. Common examples include the extension of the addition operation to the summation operation, and the extension of the...
- Summation equationSummation equationIn mathematics, a summation equation or discrete integral equation is an equation in which an unknown function appears under a summation sign. The theories of summation equations and integral equations can be unified as integral equations on time scales using time scale calculus...
- Basel problemBasel problemThe Basel problem is a famous problem in mathematical analysis with relevance to number theory, first posed by Pietro Mengoli in 1644 and solved by Leonhard Euler in 1735. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate...
–
Further reading
- Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).