2.5. Recursion and Induction 31
might be proving some property P is true of all the natural numbers.
To do so, you prove that P is true of 0, and then prove that if P
is true of some n ≥ 0, then P is also true of n + 1. To recursively
define a class of objects C, you give certain simple examples of objects
in C, and then operations that combine or extend elements of C to
give results still in C. They relate more deeply than just appearance,
though. We’ll tackle induction, then recursion, then induction again.
2.5.1. Induction on N. The basic premise of induction is that if
you can start, and once you start you know how to keep going, then
you will get all the way to the end. If I can get on the ladder, and I
know how to get from one rung to the next, I can get to the top of
Definition 2.5.1. The principle of mathematical induction, basic
form, says the following.
If S is a subset of the positive integers containing 1 such that
n ∈ S implies n + 1 ∈ S for all n, then S contains all of the posi-
tive integers. [We may need the beginning to be 0 or another value
depending on context.]
In general you want to use induction to show that some property
holds no matter what integer you feed it, or no matter what size finite
set you are dealing with. The proofs always have a base case, the case
of 1 (or wherever you’re starting). Then they have the inductive step,
the point where you assume the property holds for some unspecified
n and then show it holds for n + 1.
Example 2.5.2. Prove that for every positive integer n,
1 + 3 + 5 + . . . + (2n − 1) =
Proof. Base case: For n = 1, the equation is 1 = 12, which is true.
Inductive step: Assume that 1 + 3 + 5 + . . . + (2n − 1) =
n ≥ 1. To show that it holds for n + 1, add 2(n + 1) − 1 to each side,
in the simplified form 2n + 1.
1 + 3 + 5 + . . . + (2n − 1) + (2n + 1) =
+ 2n + 1 = (n +
Since the equation above is that of the theorem, for n+1, by induction
the equation holds for all n.