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.
