Use the algorithm in Exercise 24 to devise an algorithm for evaluating an when n is a nonnegative integer. [Hint: Use the binary expansion of n.]

MODULE 14: INDUCTION AND RECURSIVE DEFINITION/ALGORITHM Induction/Recursive Definition Algorithm Chapter Summary Mathematical Induction Strong Induction Well-Ordering Recursive Definitions Structural Induction Recursive Algorithms → 5.1 Mathematical Induction ← Climbing an Infinite Ladder Suppose we have an infinite ladder: 1. We can reach the first rung of the ladder. 2. If we can reach a particular rung of the ladder, then we can reach the next rung. From (1), we can reach the first rung. Then by applying (2), we can reach the second rung. Applying (2) again, the third rung. And so on. We can apply (2) as many times as we feel to reach any particular rung no matter the height.