Multi-Page Printing

2.5. Recursion and Induction 35 Exercise 2.5.13. Write a recursive definition of the rational func- tions in x, those functions which can be written as a fraction of two polynomials of x. Your basic objects should be x and all real numbers. We may also define functions recursively. For that, we say what f(0) is (or whatever our basic object is) and then define f(n + 1) in terms of f(n). For example, (n + 1)! = (n + 1)n!, with 0! = 1, is factorial, a recursively defined function you’ve probably seen before. We could write a recursive definition for addition of natural numbers as follows. a(0, 0) = 0 a(m + 1,n) = a(m, n) + 1 a(m, n + 1) = a(m, n) + 1 This looks lumpy but is actually used in logic in order to minimize the number of operations that we take as fundamental: this definition of addition is all in terms of successor, the plus-one function. Exercise 2.5.14. Write a recursive definition of p(m, n) = m · n, on the natural numbers, in terms of addition. Exercise 2.5.15. Write a recursive definition of f(n) = 2n32n+1, on the natural numbers. Definition 3.3.1 gives a recursively defined set of functions in which one of the closure operators gives a function defined recursively from functions already in the set. 2.5.3. Induction Again. Induction and recursion have a strong tie beyond just their resemblance. Proving a property holds of all mem- bers of a recursively defined class often requires induction. This use of induction is less codified than the induction on N we saw above. In fact, the induction in §2.5.1 is simply the induction that goes with the recursively defined set of natural numbers, as in Example 2.5.8. To work generally, the base case of the inductive argument must match the basic objects of the recursive class. The inductive step comes from the closure operations that build up the rest of the class. You are showing the set of objects that have a certain property con- tains the basic objects of the class and is closed under the operations of the class, and hence must contain the entire class.