Bounding Summations

3.1.1 Bounding Summations

We first introduce a few methods for bounding the summations that describe the running times of algorithm. The following subsections are the most frequently used techniques.

Mathematical Induction

The most basic way to prove a series equation is to use mathematical induction.

Method 3.1.1
Assume you have a series:

n ∑ f (k) = g(n) k=1

You first need to prove the equation holds for the base case, that is, f(k = 1) = g(1). Next, we assume the equation ’is’ correct, and call that Inductive Hypothesis. The last goal is to prove if it holds for (n + 1) case.

For example,

n ∑ k = 1⋅n ⋅(n+ 1)(from equation 1.7.0.14) k=1 2

Proof>
(Base)

∑1 1 k = 1 = 2 ⋅1⋅2 = 1 k=1

(Inductive Hypothesis), Assume

∑n 1 k = -⋅n ⋅(n+ 1) k=1 2

Need to prove

n∑+1 k = 1 ⋅(n+ 1)⋅(n +2) k=1 2

Sol>

n∑+1 ∑n k = k+ (n+ 1) k=1 k=1 = 1 ⋅n ⋅(n+ 1)+ (n +1) 2 = n⋅(n-+-1)+-2⋅(n+-1) 2 = n2 +-3-⋅n+-2 2 = 1 ⋅(n + 1)⋅(n + 2) 2

Thus, proved.

Bounding the Terms

Method 3.1.2
A quick upper bound on a series can be obtained by bounding each term of the series with the largest term. That is,

∑n ∑n ak ≤ aMAX k=1 = kn=1⋅a MAX

Conversely, a quick lower bound can be evaluated by bounding each term with the smallest term. That is,

∑n ∑n ak ≥ aMIN k=1 k=1 = n ⋅aMIN

Splitting Summations

Method 3.1.3
Another technique to get a bound is to express the series as the sum of two or more series by partitioning the range of the index and then to bound each of the resulting series[1]. That is,

n k0- 1 n ∑ ak = ∑ ak + ∑ ak k=1 k=1 k=k0

Approximation by Integrals

Method 3.1.4
When a function f(k) is a monotonically increasing function, the summation of f(k) can be approximated by integrals,

∫ n n ∫ n+1 f(x )dx ≤ ∑ f(k ) ≤ f(k)dx (3.1.1.1) m-1 k=m m

When f(k) is a monotonically decreasing function, the summation of f(k) can be bounded by integrals,

∫ ∫ n+1 ∑n n m f(x)dx ≤ f(k) ≤ m -1f(k)dx (3.1.1.2) k=m

For example, the integral approximation gives a tight bound for the n^th harmonic number (monotonically decreasing),

∫ ∑n 1- k+1dx- k ≥ 1 x k=1 = ln (n + 1) = Ω(ln n) ∑n 1 ∑n 1 k- = 1+ k- k=1 ∫ k=2 ≤ ndx- 1 x = ln n = O(lnn) ∑n 1- = Θ(lnn) (3.1.1.3) k=1k

[next] [front] [up]