Summation

Last updated

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.

Contents

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, [lower-alpha 1]

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.

Notation

Capital-sigma notation

The summation symbol Greek uc sigma.svg
The summation symbol

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. [lower-alpha 2]

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 , , , [1] 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. [2] 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 . [lower-alpha 3]

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 .

Special cases

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.

Formal definition

Summation may be defined recursively as follows:

, for b < a;
, for ba.

Measure theory notation

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.

Calculus of finite differences

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:

where

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 [3]

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.

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:

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.

Identities

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.

General identities

(distributivity) [4]
(commutativity and associativity) [4]
(index shift)
for a bijection σ from a finite set A onto a set B (index change); this generalizes the preceding formula.
(splitting a sum, using associativity)
(a variant of the preceding formula)
(the sum from the first term up to the last is equal to the sum from the last down to the first)
(a particular case of the formula above)
(commutativity and associativity, again)
(another application of commutativity and associativity)
(splitting a sum into its odd and even parts, for even indexes)
(splitting a sum into its odd and even parts, for odd indexes)
(distributivity)
(distributivity allows factorization)
(the logarithm of a product is the sum of the logarithms of the factors)
(the exponential of a sum is the product of the exponential of the summands)

Powers and logarithm of arithmetic progressions

for every c that does not depend on i
(Sum of the simplest arithmetic progression, consisting of the first n natural numbers.) [3] :52
(Sum of first odd natural numbers)
(Sum of first even natural numbers)
(A sum of logarithms is the logarithm of the product)
(Sum of the first squares, see square pyramidal number.) [3] :52
(Nicomachus's theorem) [3] :52

More generally, one has Faulhaber's formula for

where denotes a Bernoulli number, and is a binomial coefficient.

Summation index in exponents

In the following summations, a is assumed to be different from 1.

(sum of a geometric progression)
(special case for a = 1/2)
(a times the derivative with respect to a of the geometric progression)
(sum of an arithmetico–geometric sequence)

Binomial coefficients and factorials

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.

Involving the binomial theorem

the binomial theorem
the special case where a = b = 1
, the special case where p = a = 1 − b, which, for expresses the sum of the binomial distribution
the value at a = b = 1 of the derivative with respect to a of the binomial theorem
the value at a = b = 1 of the antiderivative with respect to a of the binomial theorem

Involving permutation numbers

In the following summations, is the number of k-permutations of n.

, where and denotes the floor function.

Others

Harmonic numbers

(that is the nth harmonic number)
(that is a generalized harmonic number)

Growth rates

The following are useful approximations (using theta notation):

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

Notes

  1. For details, see Triangular number.
  2. For a detailed exposition on summation notation, and arithmetic with sums, see Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). "Chapter 2: Sums". Concrete Mathematics: A Foundation for Computer Science (PDF) (2nd ed.). Addison-Wesley Professional. ISBN   978-0201558029.[ permanent dead link ]
  3. Although the name of the dummy variable does not matter (by definition), one usually uses letters from the middle of the alphabet ( through ) to denote integers, if there is a risk of confusion. For example, even if there should be no doubt about the interpretation, it could look slightly confusing to many mathematicians to see instead of in the above formulae involving . See also typographical conventions in mathematical formulae.

Sources

  1. "Compendium of Mathematical Symbols". Math Vault. 2020-03-01. Retrieved 2020-08-16.
  2. "Summation Notation". www.columbia.edu. Retrieved 2020-08-16.
  3. 1 2 3 4 Handbook of Discrete and Combinatorial Mathematics, Kenneth H. Rosen, John G. Michaels, CRC Press, 1999, ISBN   0-8493-0149-1.
  4. 1 2 "Calculus I - Summation Notation". tutorial.math.lamar.edu. Retrieved 2020-08-16.

Related Research Articles

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".

Binomial coefficient Positive integers that occur as coefficients in the binomial theorem

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 nk ≥ 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.

Divisor function Arithmetic function related to the divisors of an integer

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.

Mertens function

In number theory, the Mertens function is defined for all positive integers n as

Integral test for convergence

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.

Chebyshev function

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 Karatsuba Russian mathematician

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 FEEfast E-function evaluation – because it makes fast computations of the Siegel -functions possible, in particular of .

Derivative of the exponential map formula in Lie group theory

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:gG, 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: