Misplaced Pages

This is an old revision of this page, as edited by LC~enwiki (talk | contribs) at 23:45, 24 August 2002 (first draft). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A sum is the addition of two or more numbers (see arithmetic). A sum of several terms is usually written using plus symbols (+). A sum with many terms is often written using a capital sigma, which is defined as:

 b
 ∑  f(i)  =  f(a) + f(a+1) + f(a+2) + ... + f(b-1) + f(b)
i=a

The following are useful identities:

 n
 ∑  i  =  n(n+1)/2
i=1

 n
 ∑  i  =  (2n+3n+n)/6
i=0

 n
 ∑  x  =  (x -1) / (x-1)
i=0

 ∞
 ∑  x  =  1 / (1-x)
i=0

n-1   / i \      /  n  \
 ∑   |    |  =  |      |          (see binomial coefficient)
i=0   \ k /      \ k+1 /

The following are useful approximations (using theta notation):

 n
 ∑  i  =  Θ(n)    for every real constant c ≠ -1.
i=1

 n
 ∑   1/i  =  Θ(log(n))
i=1

 n
 ∑   c  =  Θ(c)   for every real constant c.
i=1

 n
 ∑   log(i)  =  Θ(n log(n))   for every real constant c ≥ 0.
i=1

 n
 ∑   log(i)  i =  Θ(n log(n))   for all real constants c ≥ 0 and d ≥ 0.
i=1

 n
 ∑   log(i)  i  b =  Θ(n log(n) b)  for all real constants c ≥ 0, d ≥ 0 and b > 1.
i=1