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.