50 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS
Extracting the quantity in the large brackets, and using the inductive hypothesis, it will
suffice to prove1 (2n+l) 1
y3n 2n+2 :S J3n+3'
Unfortunately, this inequality is false! For example, if you plug in n = I, you get
1 ( 3 ) 1
v'3^4 :S J6'
which would imply V2 :s 4/3, which is clearly absurd.
What happened? We employed wishful thinking and got burned. It happens from
time to time. The inequality that we wish to prove, while true, is very weak (i.e.,asserts very little), especially for small n. The starting hypothesis of P( I) is too weak
to lead to P(2), and we are doomed.
The solution: strengthen the hypothesis from the start. Let us replace the 3n with
3n + I. Denote the statement
(�) (�) ..
.
( 2 �: I) :s �
by Q(n). Certainly, Q(I) is true; in fact, it is an equality (1/2 = 1/v4), which is about
as sharp as an inequality can be! So let us try to prove Q(n + I) using Q(n) as the
inductive hypothesis. As before, we try the obvious algebra, and hope that we can
prove the inequality1 (2n + l) 1
J3n + 1 2n + 2
:sJ3n + 4
.
Squaring and cross-multiplying reduce this to the alleged inequality(3n +4) (4n^2 + 4n + I) :s 4(n^2 + 2n+ 1)(3n + I),
which reduces (after some tedious multiplying) to 19n :s 20n, and that is certainly true.
So we are done. _Problems and Exercises
2.3.11 Let a,b, c be integers satisfying a^2 +b^2 = c^2 •
Give two different proofs that abc must be even,
(a) by considering various parity cases;
(b) using argument by contradiction.
2.3.12 Make sure you understand Example 2.3.2 per
fectly by doing the following exercises.
(a) Prove that J3 is irrational.
(b) Prove that v'6 is irrational.
(c) If you attempt to prove J49 is irrational by us-ing the same argument as before, where does
the argument break down?
2.3.13 Prove that there is no smallest positive real
number.
2.3.14 Prove that log 10 2 is irrational.
2.3.15 Prove that v'2 + J3 is irrational.
2.3.16 Can the complex numbers be ordered? In other
words, is it possible to define a notion of "inequality"
so that any two complex numbers a+bi and c+di can