Java Reference
In-Depth Information
written f(1) + f(2) + + f(n 1) + f(n): Within a sentence, Sigma notation
is typeset as
P
i=1
f(i):
Given a summation, you often wish to replace it with an algebraic equation
with the same value as the summation. This is known as a closed-form solution,
and the process of replacing the summation with its closed-form solution is known
as solving the summation. For example, the summation
P
i=1
1 is simply the ex-
pression “1” summed n times (remember that i ranges from 1 to n). Because the
sum of n 1s is n, the closed-form solution is n. The following is a list of useful
summations, along with their closed-form solutions.
n
X
n(n + 1)
2
i =
:
(2.1)
i=1
n
X
2n
3
+ 3n
2
+ n
6
=
n(2n + 1)(n + 1)
6
i
2
=
:
(2.2)
i=1
logn
X
n = n log n:
(2.3)
i=1
1
X
1
1 a
for 0 < a < 1:
a
i
=
(2.4)
i=0
n
X
a
n+1
1
a 1
a
i
=
for a 6= 1:
(2.5)
i=0
As special cases to Equation 2.5,
n
X
1
2
i
1
1
=
2
n
;
(2.6)
i=1
and
n
X
2
i
2
n+1
1:
=
(2.7)
i=0
As a corollary to Equation 2.7,
logn
X
2
i
2
logn+1
1 = 2n 1:
=
(2.8)
i=0
Finally,
n
X
i
2
i
2
n + 2
2
n
=
:
(2.9)
i=1
The sum of reciprocals from 1 to n, called the Harmonic Series and written
H
n
, has a value between log
e
n and log
e
n+ 1. To be more precise, as n grows, the
