Discrete Mathematics for Computer Science

60 CHAPTER 1 Sets, Proof Templates, and Induction

The process continues to add decimal digits to the intial approximation for as many itera-

tions of the for loop as are required by the code. For the code shown, the final approxima-

tion is Root = 4.12310562 and Root Root = 16.9999999536.

For Square Root I, we can find an explicit formula for a bound on the error after n

iterations. Let Rn denote the value of Root after n iterations of the for loop. The error term

is defined as En = /1 - Rn for n E N.

Theorem 4. Prove that for Square Root I, the error bound Ec for R, satisfies the inequal-

ity En < 10' for each n e N.

Proof Let n 0 =0. LetT= {n eN: Rn < A1 < Rn + I O-n.

(Base step) For n = 0, the result follows, since Root is 4 and the for loop is not executed.

Clearly, 4 < -17 < 5, so 6o = /17 - 4 < 1 = 10-0. Therefore, 0 e T.

(Inductive step) Choose n > no such that n e T. Now, prove that n + 1 E T. That is,

assume Rn < 17 < Rn + 10-n, and prove that Rn+± < /17 < Rn+ 1 + 10-(n+'). By

the inductive hypothesis,

Rn < /17 < R, + 10-n = Rn + 10. 10-(n+1)

The search for Digit finds the largest integer Digit where Rn +I Digit. 10-(n+1) < -17.

Since Digit is the largest such integer,

Rn + Digit. 10-(n+l) < /17 < (Rn + Digit. 10-(n+)) + I0-(n+l)

Since Digit + 1 has the property that

(Rn + (Digit + 1). 10-(n+l))2 > 17

then

Rn + Digit. 10-(n+1) = Rn+ < VI7 < Rn + Digit. 10-(n+0) + 10-(n+1)

= Rn+ 1 + 10-0+1)

as desired, and n + 1 e T.

Therefore, T = N by the Principle of Mathematical Induction. U

Square Root II

The Square Root II algorithm produces an approximation of the square root of an inte-

ger by generating approximations that are alternately larger than the square root and then

smaller than the square root. Each iteration of the procedure, however, brings the value of

the approximation closer to the true value of the square root.