In mathematics, summation is the addition of a sequence of any kind of numbers, called addends or summands; the result is their sum or total. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, polynomials and, in general, elements of any type of mathematical objects on which an operation denoted "+" is defined.
Summations of infinite sequences are called series. They involve the concept of limit, and are not considered in this article.
The summation of an explicit sequence is denoted as a succession of additions. For example, summation of [1, 2, 4, 2] is denoted 1 + 2 + 4 + 2, and results in 9, that is, 1 + 2 + 4 + 2 = 9. Because addition is associative and commutative, there is no need of parentheses, and the result is the same irrespective of the order of the summands. Summation of a sequence of only one element results in this element itself. Summation of an empty sequence (a sequence with no elements), by convention, results in 0.
Very often, the elements of a sequence are defined, through regular pattern, as a function of their place in the sequence. For simple patterns, summation of long sequences may be represented with most summands replaced by ellipses. For example, summation of the first 100 natural numbers may be written as 1 + 2 + 3 + 4 + ⋯ + 99 + 100. Otherwise, summation is denoted by using Σ notation, where is an enlarged capital Greek letter sigma. For example, the sum of the first n natural numbers can be denoted as
For long summations, and summations of variable length (defined with ellipses or Σ notation), it is a common problem to find closed-form expressions for the result. For example,
Although such formulas do not always exist, many summation formulas have been discovered—with some of the most common and elementary ones being listed in the remainder of this article.
Mathematical notation uses a symbol that compactly represents summation of many similar terms: the summation symbol, , an enlarged form of the upright capital Greek letter sigma. This is defined as
where i is the index of summation; ai is an indexed variable representing each term of the sum; m is the lower bound of summation, and n is the upper bound of summation. The "i = m" under the summation symbol means that the index i starts out equal to m. The index, i, is incremented by one for each successive term, stopping when i = n.
This is read as "sum of ai, from i = m to n".
Here is an example showing the summation of squares:
In general, while any variable can be used as the index of summation (provided that no ambiguity is incurred), some of the most common ones include letters such as , , , and ; the latter is also often used for the upper bound of a summation.
Alternatively, index and bounds of summation are sometimes omitted from the definition of summation if the context is sufficiently clear. This applies particularly when the index runs from 1 to n.For example, one might write that:
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 over all (integers) in the specified range,
is the sum of over all elements in the set , and
is the sum of over all positive integers dividing .
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 .
It is possible to sum fewer than 2 numbers:
These degenerate cases are usually only used when the summation notation gives a degenerate result in a special case. For example, if in the definition above, then there is only one term in the sum; if , then there is none.
Summation may be defined recursively as follows:
In the notation of measure and integration theory, a sum can be expressed as a definite integral,
where is the subset of the integers from to , and where is the counting measure.
Given a function f that is defined over the integers in the interval [m, n], the following equation holds:
This is the analogue of the fundamental theorem of calculus in calculus of finite differences, which states that:
is the derivative of f.
An example of application of the above equation is the following:
Using binomial theorem, this may be rewritten as:
The above formula is more commonly used for inverting of the difference operator , defined by:
where f is a function defined on the nonnegative integers. Thus, given such a function f, the problem is to compute the antidifference of f, a function such that . That is, This function is defined up to the addition of a constant, and may be chosen as
There is not always a closed-form expression for such a summation, but Faulhaber's formula provides a closed form in the case where and, by linearity, for every polynomial function of n.
Many such approximations can be obtained by the following connection between sums and integrals, which holds for any increasing function f:
and for any 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 formulae below involve finite sums; for infinite summations or finite summations of expressions involving trigonometric functions or other transcendental functions, see list of mathematical series.
More generally, one has Faulhaber's formula for
where denotes a Bernoulli number, and is a binomial coefficient.
In the following summations, a is assumed to be different from 1.
There exist very many summation identities involving binomial coefficients (a whole chapter of Concrete Mathematics is devoted to just the basic techniques). Some of the most basic ones are the following.
In the following summations, is the number of k-permutations of n.
The following are useful approximations (using theta notation):
In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and is given by the formula
In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, mathematical analysis. Series are used in most areas of mathematics, even for studying finite structures through generating functions. In addition to their ubiquity in mathematics, infinite series are also widely used in other quantitative disciplines such as physics, computer science, statistics and finance.
In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius.
In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships on the Riemann zeta function and the Eisenstein series of modular forms. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities; these are treated separately in the article Ramanujan's sum.
In number theory, the Mertens function is defined for all positive integers n as
In mathematics, the integral test for convergence is a method used to test infinite series of monotonous terms for convergence. It was developed by Colin Maclaurin and Augustin-Louis Cauchy and is sometimes known as the Maclaurin–Cauchy test.
Multi-index notation is a mathematical notation that simplifies formulas used in multivariable calculus, partial differential equations and the theory of distributions, by generalising the concept of an integer index to an ordered tuple of indices.
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 finite limit.
In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that generalises the Kronecker delta, which is the Iverson bracket of the statement x = y. It maps any statement into a function of the free variables in it, that takes the value one for the values of the variables for which the statement is true, and takes the value zero otherwise. It is generally denoted by putting the statement inside square brackets:
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.
In mathematics, the Chebyshev function is either of two related functions. The first Chebyshev functionϑ(x) or θ(x) is given by
Ramanujan summation is a technique invented by the mathematician Srinivasa Ramanujan for assigning a value to divergent infinite series. Although the Ramanujan summation of a divergent series is not a sum in the traditional sense, it has properties that make it mathematically useful in the study of divergent infinite series, for which conventional summation is undefined.
This is a summary of differentiation rules, that is, rules for computing the derivative of a function in calculus.
Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.
In mathematics, the FEE method is the method of fast summation of series of a special form. It was constructed in 1990 by Ekaterina A. Karatsuba and was called FEE – fast E-function evaluation – because it makes fast computations of the Siegel -functions possible, in particular of .
In the theory of Lie groups, the exponential map is a map from the Lie algebra g of a Lie group G into G. In case G is a matrix Lie group, the exponential map reduces to the matrix exponential. The exponential map, denoted exp:g → G, is analytic and has as such a derivative d/dtexp(X ):Tg → TG, where X(t) is a C1 path in the Lie algebra, and a closely related differential dexp:Tg → TG.
In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.
In number theory, the prime omega functions and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. For example, if we have a prime factorization of of the form for distinct primes , then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.
The purpose of this page is to catalog new, interesting, and useful identities related to number-theoretic divisor sums, i.e., sums of an arithmetic function over the divisors of a natural number , or equivalently the Dirichlet convolution of an arithmetic function with one: