Bounding Summations

3.7.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.7.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 1 k = 2 ⋅n ⋅(n + 1)(from equation 1.2.14) k=1

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 = 2 ⋅(n + 1)⋅(n + 2)

Thus, proved.

Bounding the Terms

Method 3.7.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 k=1 = n ⋅aMAX

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

∑n ∑n ak ≥ aMIN k=1 = kn=1⋅a MIN

Splitting Summations

Method 3.7.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∑ k∑0- 1 ∑n ak = ak + ak k=1 k=1 k=k0

Approximation by Integrals

Method 3.7.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.7.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 f(x)dx ≤ ∑ f(k) ≤ f(k)dx (3.7.2) m k=m m -1

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.7.3) k=1k

[next] [front] [up]