Mathematics for Computer Science

14.3. Approximating Sums 411

Similarly,f isstrictly decreasingwhen

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

and it isweakly decreasing^6 when

x < yIMPLIESf.x/f.y/:

For example, 2 xand

p
xare strictly increasing functions, while maxx;2anddxe
are weakly increasing functions. The functions1=xand 2 xare strictly decreasing,
while min1=x;1=2andb1=xcare weakly decreasing.

Theorem 14.3.2.LetfWRC!RCbe a weakly increasing function. Define

SWWD

Xn

iD 1

f.i/ (14.15)

and

IWWD

Zn

1

f.x/dx:

Then
ICf.1/SICf.n/: (14.16)

Similarly, iffis weakly decreasing, then

ICf.n/SICf.1/:

Proof. Supposef WRC !RCis weakly increasing. The value of the sumS
in (14.15) is the sum of the areas ofnunit-width rectangles of heightsf.1/;f.2/;:::;f.n/.
This area of these rectangles is shown shaded in Figure 14.1.
The value of
ID

Zn

1

f.x/dx

is the shaded area under the curve off.x/from 1 tonshown in Figure 14.2.
Comparing the shaded regions in Figures 14.1 and 14.2 shows thatSis at least
Iplus the area of the leftmost rectangle. Hence,

SICf.1/ (14.17)

This is the lower bound forSgiven in (14.16).
To derive the upper bound forSgiven in (14.16), we shift the curve off.x/
from 1 tonone unit to the left as shown in Figure 14.3.

(^6) Weakly decreasing functions are usually callednonincreasing.