9780023606922, Chapter 2 4, Problem 23E

Prévia do material em texto

Chapter 2.4, Problem 23E Step-by-step solution Step 1 of 5 Specified algorithm: expl (a,n) if (n == 1) return exp1(a,m) X return a m = n/2 Step 2 of 5 Consider to be the number of multiplications required to compute The recurrence relation for is: = If If n n even odd n n #1 > 1 We have to prove that = n 1 for 2 every positive integer, n by the method of iteration. Step 3 of 5 Basic Step: We have to check whether the expression is true for As there are no multiplications done when n = it simply returns a. Therefore the expression is true for Step 4 of 5 Inductive step: Assume that it is true for then Now, we have to check whether the expression is true for Since - is an even number the recurrence relation that will be applied is: Thus, (1) Step 5 of 5 According to the inductive assumption = k On substituting the value of in equation (1), we get =2k-2+1 Thus, it is true for = in the similar way it is true for all odd values of n. Therefore the expression = n is true for all positive integers n by the principle of mathematical induction. Hence it is proved.