Discrete Mathematics for Computer Science

74 CHAPTER 1 Sets, Proof Templates, and Induction

FastPower (2, 5)

\return^32

base expont

call: 2 5

\return

32

base expont

call 2: 4 2

return 16

call 3: base expont

16 1

\return^1

base expont

call4: 16 1

Figure 1.19 Flow of control for FastPower (2, 5).

and every exponent. Using the Strong Form of Mathematical Induction, we now prove that

the algorithm is correct for all cases.

Theorem 2. The FastPower algorithm returns the value base' for base E R - {0}, and

n E N.

Proof. The proof is by induction on the value of n. Let no = 0 and

T = {n e N : for every base e R - {0}, FastPower(base, n) = base}

Prove by the Strong Form of Mathematical Induction that T = N.

(Base step) For n = 0, the algorithm returns 1, as required. So, 0 G T.

(Inductive step) Let n > 0. Assume that for all k such that 0 < k < n, k E T. Now,

prove that n E T.

This case breaks into two subcases:

Case 1: n is odd. So, n = 2k +± for some k e N. Clearly, 0 < k <n. By familiar

properties of exponentiation,

base^2 k+l = base base

(^2) k
= base. (base
(^2) )k
By the inductive hypothesis, since k < n, the algorithm correctly computes bk for any b.
In particular, it computes (base^2 ))k; thus, base. (base^2 )k = base^2 k+l.
Case 2: n is even. The proof is analogous to the proof of Case 1. In either case, n E T.
By the Strong Form of Mathematical Induction, T = N. 0
FastPower is actually used in many computer science applications when the exponent
is known to be an integer. Special computer chips are used in cryptography for doing