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.
Previous Page Next Page