Mathematics for Computer Science

13.3. Approximating Sums 513

0 1 2 3   



^

n� 2 n� 1 n

f.n/

f.n�1/

f.3/

f.2/

f.1/

Figure 13.1P The area of theith rectangle isf.i/. The shaded region has area
n
iD 1 f.i/.

For example, 2 xand

p
xare strictly increasing functions, while maxfx;2gand
dxeare weakly increasing functions. The functions1=xand 2 xare strictly de-
creasing, while minf1=x;1=2gandb1=xcare weakly decreasing.

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

SWWD

Xn

iD 1

f.i/ (13.15)

and

IWWD

Zn

1

f.x/dx:

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

Similarly, iffis weakly decreasing, then

ICf.n/SICf.1/:

Proof. Supposef WRC !RCis weakly increasing. The value of the sumS
in (13.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 13.1.
The value of
ID

Zn

1

f.x/dx

is the shaded area under the curve off.x/from 1 tonshown in Figure 13.2.