1.2. The Natural Numbers 13

If Pn is true, then the first term on the right is divisible by 3. The second term on

the right is also divisible by 3, since 5 − 2 = 3. This implies that 5n+1 − 2n+1 is

divisible by 3 and, hence, that Pn+1 is true. This completes the induction step.

By induction (that is, by Theorem 1.2.1), Pn is true for all n.

Example 1.2.11. Define a sequence {xn} of real numbers by setting x1 = 1 and

using the recursion relation

(1.2.6) xn+1 =

√

xn + 1.

Show that this is an increasing sequence of positive numbers less than 2.

Solution: The function f(x) =

√

x + 1 may be regarded as a function from

the set of positive real numbers into itself. We can apply Theorem 1.2.3, with each

of the functions fn equal to f, to conclude that a sequence {xn} is uniquely defined

by setting x1 = 1 and imposing the recursion relation (1.2.6).

Let Pn be the proposition that xn xn+1 2. We will prove that Pn is true

for all n by induction.

Base case: P1 is the statement x1 x2 2. Since x1 = 1 and x2 =

√

2, this is

true.

Induction step: Suppose Pn is true for some n. Then xn xn+1 2. If we

add one and take the square root, this becomes

√

xn + 1 xn+1 + 1

√

3.

Using the recursion relation (1.2.6), this yields

xn+1 xn+2

√

3.

Since

√

3 2, Pn+1 is true. This completes the induction step.

We conclude that Pn is true for all n ∈ N.

Binomial Formula. The proof of the binomial formula is an excellent example

of the use of induction.

We will use the notation

n

k

=

n!

k!(n − k)!

.

This is the number of ways of choosing k objects from a set of n objects.

Theorem 1.2.12. If x and y are real numbers and n ∈ N, then

(x +

y)n

=

n

k=0

n

k

xkyn−k.

Proof. We prove this by induction on n.

Base case: Since

1

0

and

1

1

are both 1, the binomial formula is true when

n = 1.