Page 385 - Discrete Mathematics and Its Applications

364 5 / Induction and Recursion

problem with a sequence at most half as long. If have we never encountered the search term x,
our algorithm returns the value 0. We express this recursive version of a binary search algorithm
as Algorithm 6. ▲

ALGORITHM 6 A Recursive Binary Search Algorithm.

procedure binary search(i,j,x: i, j, x integers, 1 ≤ i ≤ j ≤ n)
m := (i + j)/2
if x = a m then
return m
else if (x < a m and i< m) then
return binary search(i, m − 1,x)
else if (x > a m and j> m) then
return binary search(m + 1,j,x)
else return 0
{output is location of x in a 1 ,a 2 ,...,a n if it appears; otherwise it is 0}

Proving Recursive Algorithms Correct

Mathematical induction, and its variant strong induction, can be used to prove that a recursive
algorithm is correct, that is, that it produces the desired output for all possible input values.
Examples 7 and 8 illustrate how mathematical induction or strong induction can be used to
prove that recursive algorithms are correct. First, we will show that Algorithm 2 is correct.

EXAMPLE 7 Prove that Algorithm 2, which computes powers of real numbers, is correct.

Solution: We use mathematical induction on the exponent n.

BASIS STEP: If n = 0, the first step of the algorithm tells us that power (a, 0) = 1. This is
0
correct because a = 1 for every nonzero real number a. This completes the basis step.
k
INDUCTIVE STEP: The inductive hypothesis is the statement that power (a, k) = a for all
a = 0 for an arbitrary nonnegative integer k. That is, the inductive hypothesis is the statement
k
that the algorithm correctly computes a . To complete the inductive step, we show that if the
inductive hypothesis is true, then the algorithm correctly computes a k+1 . Because k + 1isa
positive integer, when the algorithm computes a k+1 , the algorithm sets power (a, k + 1) =
k
a· power (a, k). By the inductive hypothesis, we have power (a, k) = a ,so power (a, k + 1) =
k
a · power (a, k) = a · a = a k+1 . This completes the inductive step.
We have completed the basis step and the inductive step, so we can conclude thatAlgorithm
n
2 always computes a correctly when a = 0 and n is a nonnegative integer. ▲
Generally, we need to use strong induction to prove that recursive algorithms are correct,
rather than just mathematical induction. Example 8 illustrates this; it shows how strong induction
can be used to prove that Algorithm 4 is correct.

EXAMPLE 8 Prove that Algorithm 4, which computes modular powers, is correct.

Solution: We use strong induction on the exponent n.
BASIS STEP: Let b be an integer and m an integer with m ≥ 2. When n = 0, the algorithm sets
0
mpower(b,n,m) equal to 1. This is correct because b mod m = 1. The basis step is complete.