Summation

This article is about the mathematics of nite summation. the reader easily guesses the pattern; however, for more
For innite summation, see Series (mathematics). For complicated patterns, one needs to be precise about the
other uses, see Summation (disambiguation).
rule used to nd successive terms, which can be achieved
by using the summation operator "". Using this sigma
notation the above summation is written as:
In mathematics, summation (symbol: ) is the addition
of a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right,
100
any intermediate result is a partial sum, prex sum, or
i.
running total of the summation. The numbers to be
i=1
summed (called addends, or sometimes summands) may
be integers, rational numbers, real numbers, or complex The value of this summation is 5050. It can be found
numbers. Besides numbers, other types of values can be without performing 99 additions, since it can be shown
added as well: vectors, matrices, polynomials and, in gen- (for instance by mathematical induction) that
eral, elements of any additive group (or even monoid).
For nite sequences of such elements, summation always
n
produces a well-dened sum.

n(n + 1)
i=
The summation of an innite sequence of values is called
2
a series. A value of such a series may often be dened by i=1
means of a limit (although sometimes the value may be for all natural numbers n.[1] More generally, formulae exinnite, and often no value results at all). Another notion ist for many summations of terms following a regular patinvolving limits of nite sums is integration. The term tern.
summation has a special meaning related to extrapolation
The term "indenite summation" refers to the search for
in the context of divergent series.
an inverse image of a given innite sequence s of values
The summation of the sequence [1, 2, 4, 2] is an for the forward dierence operator, in other words for a
expression whose value is the sum of each of the mem- sequence, called antidierence of s, whose nite dierbers of the sequence. In the example, 1 + 2 + 4 + 2 = ences are given by s. By contrast, summation as discussed
9. Because addition is associative, the sum does not de- in this article is called denite summation.
pend on how the additions are grouped, for instance (1 +
2) + (4 + 2) and 1 + ((2 + 4) + 2) both have the value 9; When it is necessary to clarify that numbers are added
[2]
therefore, parentheses are usually omitted in repeated ad- with their signs, the term algebraic sum is used. For
ditions. Addition is also commutative, so permuting the example, in electric circuit theory Kirchhos circuit laws
terms of a nite sequence does not change its sum (for consider the algebraic sum of currents in a network of
innite summations this property may fail; see Absolute conductors meeting at a point, assigning opposite signs to
currents owing in and out of the node.
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 diculty if the
sequence has fewer 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: 1 + 2 + 3 + 4 + ... + 99 + 100. In this case

1 Notation
1.1 Capital-sigma notation
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 dened as:
n

i=m

ai = am + am+1 + am+2 + + an1 + an

FORMAL DEFINITION

f (x)

xS

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

(d)

d|n

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

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

is the same as

The capital sigma

where i represents the index of summation; ai is an indexed variable representing each successive term in the
series; 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 1 for each successive
term, stopping when i = n.[3]

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

.

Here is an example showing the summation of exponen1.2

tial terms (all terms to the power of 2):

Special cases

It is possible to sum fewer than 2 numbers:

6

i=3

If the summation has one summand x , then the evaluated sum is x .

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

If the summation has no summands, then the evaluated sum is zero, because zero is the identity for
addition. This is known as the empty sum.

i2 = 32 + 42 + 52 + 62 = 86.

These degenerate cases are usually only used when the

summation notation gives a degenerate result in a special
=
case. For example, if n = m in the denition above, then
i=1
there is only one term in the sum; if n = m 1 , then
One often sees generalizations of this notation in which there is none.
an arbitrary logical condition is supplied, and the sum is
intended to be taken over all values satisfying the condition. For example:

a2i

a2i .

2 Formal denition

f (k)

Summation may be dened recursively as follows

0k<100

is the sum of f (k) over all (integers) k in the specied

range,

g(i) = 0 , for b < a.

b1
i=a g(i) = g(b) +
i=a g(i) , for b a.

i=a

Measure theory notation

since the right hand side is by denition the limit for n

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

f (k) =
f d

6 Identities

[a,b]

k=a

where [a, b] is the subset of the integers from a to b , and

The formulae below involve nite sums; for innite sumwhere is the counting measure.
mations or nite summations of expressions involving
trigonometric functions or other transcendental functions,
see list of mathematical series.

Fundamental theorem of discrete

calculus

6.1 General manipulations

t

Indenite sums can be used to calculate denite sums with

the formula:[5]

f (k) =

f (b + 1)

C f (n) = C
is a constant

f (a)

k=a

Approximation by denite integrals

t
t
f (n)

n=s
n=s g(n)
t
n=s [f (n) g(n)]

n=s

s=a1

s=a

b+1

f (s) ds
s=a

i=a

n=j+1

ai,j =

f (s) ds.
s=a1

For more general approximations, see the Euler

Maclaurin formula.

z1

n=0

i=0

m n

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 denition of the corresponding denite integral. One can therefore expect that for instance
) b
n1 (
ba
ba

f (x) dx,
f a+i
n i=0
n
a

f (n) =

l1

t
n=s

k1

j=l0

i=k0

ai,j

i=k

f (n)

j=k

ai,j

t
t
f (2n) +
n=0
n=0 f (2n + 1)
2t+1
f
(n)
n=0

f (i)

j=l0

a
=
kjin
n i,j
n
j=k
i=j ai,j

decreasing function f:

l1

i=k0

f (s) ds.

i=a

f (n) +

k 1

b+1

f (i)

f (n p)

f (n) =
mA f ((m)) , for a
bijection from a nite set A onto a nite set
B; this generalizes the preceding formula.
j

n=s+p

nB

n=s

f (s) ds

t+p

f (n) =

increasing function f:

f (n) , where C

n=s

t
t
f (n)
+
n=s g(n)
n=s
t
[f
(n)
+
g(n)]
n=s

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

n=s

i=s

t
n=s

j=t

k=0

n=s

f (n)]

)(
ak

ai cj =

ln f (n) = ln

c[

f (z n + i) =

k=0

i=s

t
n=s

t
n=s

)
bk

zt+z1
n=0

ai

f (n)

j=t cj

f (n)

cf (n)

2n
k

k=0 i=0

ai bki

n1

k=0

(
ak

2nk

i=n+1

bi + bk

2nk

i=n+1

ai

6.2

Some summations of polynomial expressions

n

i=m 1 = n + 1 m

1
i=1 i
1
i=1 ik

Hnk

i=0

n1
i=0

anan +(n1)an+1
(1a)2

iai =

i2i = 2 + (n 2)2n (special case when

a = 2)

= Hn (See Harmonic number)

n1

GROWTH RATES

n1

= 2

i
i=0 2i

(See Generalized harmonic

1/2)

n+1
2n1

(special case when a =

number)
n

=
i=m i
(n+1m)(n+m)
2

n(n+1)
2

m(m1)
2
(see arithmetic series)

There exist enormously many summation identities

involving binomial coecients (a whole chapter of
Concrete Mathematics is devoted to just the basic techniques). Some of the most basic ones are the following.

n(n + 1)
i=
i=
2
i=0
i=1
n

i2 = n(n+1)(2n+1)
=
6
square pyramidal number)
i=0

3
i=0 i =
n
2
[ i=1 i]

n
4

n
2

i4 =
n3
+ 3

i=0

n(n+1)
2

)2
=

n3
3

+ n2 + n6 (see

n4
4

n3
2

n2
4

n
i=1

n
2

n(n+1)(2n+1)(3n +3n1)
30
n
30

n5
5

k=1

where Bk denotes a Bernoulli number (see Faulhabers

formula).
The following formulae are manipulations of

i=0
+

(n)
i

= 2n

( )
i ni = n2n1
i!
( )

i
i=0 k

(n)
i

i=0 n Pi

= n! e,

(n+1)
k+1

(n) (ni) i
b = (a + b)n , the binomial
i a
theorem

i=0

n
i=0

i i! = (n + 1)! 1

i=1 i+k Pk+1

(n+k+1)!
(n1)!(k+2)

( n )2

i =
i

n
i=1

j=0 (i

+ j) =

i=0

i=0

i=0

generalized to begin a series at any natural number value

(i.e., m N ):
n
n
2
( i=m i) = i=m (i3 im(m 1))
n
i=m

6.3

n
i=0

( )
p
n

(n + 1)p+1
Bk
p
p
i =
+
(n+1)pk+1 ,
p
+
1
p

k
+
1
k
i=0

6.4 Some summations involving binomial

coecients and factorials

n
n
2
i3 = ( i=m i) +m(m1) i=m i

Some summations involving exponential terms

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

n1
i=m

ries)

n1

ai =

am an
1a

(m < n; see geometric se-

ai = 1a
1a (geometric series with starting index i = 0 )
i=0

(m+i1)
i

(m+n)
n

7 Growth rates
The following are useful approximations (using theta notation):
n
i=1

ic (nc+1 ) for real c greater than 1

1
i=1 i (log n) (See Harmonic number)
i
n
i=1 c (c ) for real c greater than 1
n
c
(n log(n)c ) for noni=1 log(i)

negative real c
n
c d
d+1
log(n)c ) for noni=1 log(i) i (n
negative real c, d
n
c
d
i
d
c
n
i=1 log(i) i b (n log(n) b )
for non-negative real b > 1, c, d

See also
Checksum
Einstein notation
Iterated binary operation
Kahan summation algorithm
Product (mathematics)

Notes

[1] For details, see Triangular number.

[2] Oxford English Dictionary, 2nd ed. - algebraic (esp. of a
sum): taken with consideration of the sign (plus or minus)
of each term.
[3] 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 (2nd Edition) (PDF). Addison-Wesley Professional.
ISBN 978-0201558029.
[4] Although the name of the dummy variable does not matter
(by denition), one usually uses letters from the middle of
the alphabet ( i through q ) 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 x instead of k in
the above formulae involving k . See also typographical
conventions in mathematical formulae.
[5] Handbook of discrete and combinatorial mathematics,
Kenneth H. Rosen, John G. Michaels, CRC Press, 1999,
ISBN 0-8493-0149-1

10

Further reading

Nicholas J. Higham, "The accuracy of oating point

summation", SIAM J. Scientic Computing 14 (4),
783799 (1993).

11

External links

Media related to Summation at Wikimedia Commons

Summation at PlanetMath.org.
Moriarty, Philip; Bowley, Roger (2009). "
Summation (and Fourier Analysis)". Sixty Symbols.
Brady Haran for the University of Nottingham.

12

12
12.1

TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES

Text and image sources, contributors, and licenses

Text

Summation Source: https://en.wikipedia.org/wiki/Summation?oldid=715008887 Contributors: Hajhouse, Patrick, Michael Hardy, Fuzzie,

TakuyaMurata, Stevan White, Stevenj, Darkwind, Stan Lioubomoudrov, Furrykef, Hyacinth, David Shay, Olathe, Fredrik, Lowellian,
Bkell, Giftlite, BenFrantzDale, Ravn, LucasVB, Simoneau, Topaz, Ehamberg, Abdull, Canterbury Tail, MichaelMcGun, Rich Farmbrough, MrMALevin, Elwikipedista~enwiki, Syp, EmilJ, Alxndr, Smalljim, Per Olofsson, Vystrix Nexoth, Tsirel, Jumbuck, Musiphil,
Alansohn, Gary, Anders Kaseorg, Wicko3, Sligocki, Kbolino, Oleg Alexandrov, Woohookitty, Shreevatsa, Georgia guy, Igny, LOL, Marc
K, MattGiuca, Pol098, MFH, Mandarax, Edison, Drbogdan, NatusRoma, Salix alba, The wub, Chobot, DVdm, YurikBot, Wavelength,
Lucinos~enwiki, Buzzert, Chick Bowen, Nick, Iancarter, Whitelined, DerHannes, Jverkoey, Hirak 99, Gesslein, Bo Jacoby, Finell, InverseHypercube, KnowledgeOfSelf, Melchoir, Misantropo, DTM, CapitalSasha, BiT, David.coallier, Tyciol, Mgccl, Octahedron80, NYKevin,
Nick Levine, Atropos, Berland, Nixeagle, Calbaer, BUF4Life, Mini-Geek, Akshaysrinivasan, Dvagner37, TheHorsesMouth, Jemalonie,
Jim.belk, Iridescent, Dreftymac, RekishiEJ, JayHenry, Yanah, Bons, Doctormatt, Cydebot, Torc2, Abtract, Xantharius, Thijs!bot, N5iln,
Dfrg.msc, Escarbot, LachlanA, Mentisto, Thadius856, Luna Santin, JAnDbot, Connormah, VoABot II, Twisted86, Singularity, Zenomax,
Qtax, Avicennasis, Meatballhat, Jump o duck, Allstarecho, David Eppstein, Gwern, Highegg, R'n'B, J.delanoy, Captain panda, Robert
Illes, NewEnglandYankee, Fylwind, Fooghter20x, G2thef, VolkovBot, Jimothy 46, Classical geographer, Philip Trueman, TXiKiBoT,
Anonymous Dissident, Salvar, Geometry guy, Mouse is back, Kmhkmh, Falcon8765, Tomaxer, NHRHS2010, Drschawrz, Coco5374,
Botev, SieBot, Portalian, Gerakibot, Happysailor, Flyer22 Reborn, Paolo.dL, MiNombreDeGuerra, Lightmouse, ClueBot, JP.MartinFlatin, Niceguyedc, Excirial, JNLII, MickMacNee, SchreiberBike, Mr.Netrix, Marc van Leeuwen, DisasterManX, Avoided, SilvonenBot, Vanessa-Hudgens123 rocks, ClculIntegral, Addbot, Melab-1, Download, LaaknorBot, SamatBot, Xanstheman, Teles, Zorrobot,
, Yobot, Ptbotgourou, Gtz, Crandel, Materialscientist, DX-MON, Parkyere, Srich32977, GrouchoBot, Seeleschneider, FrescoBot, Showgun45, Tkuvho, Pinethicket, Kiefer.Wolfowitz, , Master lan, IVAN3MAN, FoxBot, Naftalip, Vrenator, Komsaslt, Smarty02,
DARTH SIDIOUS 2, Alph Bot, ToneDaBass, John of Reading, Davejohnsan, Solarra, Slawekb, Bethnim, Ryan moser, Chharvey, Zhen
Zhen, Quondum, D.Lazard, Jay-Sebastos, Eregontp, Js2794, ClueBot NG, Ninedotnine, Baseball Watcher, Degarcia, Mesoderm, Loadedsalt, Oddbodz, Edgetitleman, Titodutta, Wbm1058, Eleruin, BG19bot, AvocatoBot, Atomician, Anaverageaopser, Xanbkn, Sparkie82,
, Megestic unicorn, Oscar45596524, Pawe Ziemian, Jeremy112233, EuroCarGT, Stephan Kulla, Eptied, Brirush,
Hoppeduppeanut, Jenny0787, Minmx, Arashaneh, My name is not dave, JESii, JacobRodrigues, Monkbot, Bub250, Verdana Bold, Qwertyuiop555, SourceMath, SourceAlpha, Chirag2506 and Anonymous: 302

12.2

Images

File:Greek_uc_sigma.svg Source: https://upload.wikimedia.org/wikipedia/commons/e/e7/Greek_uc_sigma.svg License: Public domain

Contributors: ? Original artist: ?

12.3

Content license

Creative Commons Attribution-Share Alike 3.0