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

the ladder.

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) =

n2.

Proof. Base case: For n = 1, the equation is 1 = 12, which is true.

Inductive step: Assume that 1 + 3 + 5 + . . . + (2n − 1) =

n2

for some

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) =

n2

+ 2n + 1 = (n +

1)2

Since the equation above is that of the theorem, for n+1, by induction

the equation holds for all n.