Mathematics for Computer Science

Chapter 14 Sums and Asymptotics410

Solving this system gives the solutionaD 1=3,b D1=2,c D 1=6,d D 0.

Therefore,if our initial guess at the form of the solution was correct, then the

summation is equal ton^3 =3Cn^2 =2Cn=6, which matches equation 14.14.

The point is that if the desired formula turns out to be a polynomial, then once

you get an estimate of thedegreeof the polynomial, all the coefficients of the

polynomial can be found automatically.

Be careful! This method let’s you discover formulas, but it doesn’t guarantee

they are right! After obtaining a formula by this method, it’s important to go back

andproveit using induction or some other method, because if the initial guess at

the solution was not of the right form, then the resulting formula will be completely

wrong! A later chapter will describe a method based on generating functions that

does not require any guessing at all.

14.3 Approximating Sums

Unfortunately, it is not always possible to find a closed-form expression for a sum.

For example, consider the sum

SD

Xn

iD 1

p

i:

No closed form expression is known forS.

In such cases, we need to resort to approximations forSif we want to have a

closed form. The good news is that there is a general method to find closed-form

upper and lower bounds that work for most any sum. Even better, the method is

simple and easy to remember. It works by replacing the sum by an integral and

then adding either the first or last term in the sum.

Definition 14.3.1.A functionf WRC!RCisstrictly increasingwhen

x < yIMPLIESf.x/ < f.y/;

and it isweakly increasing^5 when

x < yIMPLIESf.x/f.y/:

(^5) Weakly increasing functions are usually callednondecreasingfunctions. We will avoid this
terminology to prevent confusion between being a nondecreasing function and the much weaker
property ofnotbeing a decreasing function.