116
Proofs, Induction, and Number Theory
For the first step of the induction process, it may be appropriate to begin at 0
or at 2 or 3 instead of at 1. The same principle applies, no matter where you first
hop on the ladder.
eXAMPLe 17
Prove that n
2
> 3n for n ≥ 4.
Here we should use induction and begin with a basis step of P(4). (Testing
values of n = 1, 2, and 3 shows that the inequality does not hold for these values.)
P(4) is the inequality 4
2
> 3(4), or 16 > 12, which is true. The inductive hypothesis is that k
2
> 3k and that k ≥ 4, and we want to show that (k + 1)
2
> 3(k + 1).
(k + 1)
2
= k
2
+ 2k + 1
> 3k + 2k + 1     (by the inductive hypothesis)
≥ 3k + 8 + 1       (because k ≥ 4)
= 3k + 9
> 3k + 3         (because 9 > 3)
= 3(k + 1)
In this proof we used the fact that 3k + 9 > 3k + 3. Of course, 3k + 9 is
greater than lots of things, but 3k + 3 is what gives us what we want. In an induction proof, because we know exactly what we want as the result, we can let that
guide us as we manipulate algebraic expressions.
PrACTiCe 8 Prove that for all n > 1,
2
n+1
< 3
n
■
eXAMPLe 18
Prove that for any positive integer n, the number 2
2n
– 1 is divisible by 3.
The basis step is to show P(1), that 2
2(1)
− 1 = 4 − 1 = 3 is divisible by 3.
Clearly this is true.
We assume that 2
2k
– 1 is divisible by 3, which means that 2
2k
– 1 = 3m for
some integer m, or 2
2k
= 3m + 1 (this little rewriting trick is the key to these
“ divisibility” problems). We want to show that 2
2(k+1)
– 1 is divisible by 3.
2
2(k+1)
− 1 = 2
2k+2
− 1
= 2
2 # 2
2k
− 1
= 2
2
(3m + 1) − 1     (by the inductive hypothesis)
= 12m + 4 − 1
= 12m + 3
= 3(4m + 1)          where 4m + 1 is an integer
Thus 2
2(k+1)
− 1 is divisible by 3.
Misleading claims of proof by induction are also possible. When we prove
the truth of P(k + 1) without relying on the truth of P(k), we have done a direct proof of P(k + 1) where k + 1 is arbitrary. The proof is not invalid, but it