178 METHODS OF MATHEMATICAL PROOF, PART 1 Chapter 5
5.4 Proof by Mathematical Induction
Proof by mathematical induction is a special method of proof, appropriate
for use in particular situations. In this article we introduce the principle
of mathematical induction and discuss under what circumstances and
exactly how this important principle is applied. The following example
gives several statements that, it turns out, are theorems that are provable
by mathematical induction.
EXAMPLE 1 Test the truth of each of the following statements for at least
five particular elements of the specified universal set:(a) For all positive integers n, 4 divides 5" - 1.
(b)^1 +^2 +^3 + + n = [n(n + 1)]/2 for any n = 1,2,3,....
(c) If n E N and n^2 5, then 4"^2 n4.
(d) If f,, f2,... , f, are n functions differentiable on R, where n is an
arbitrary positive integer, then their sum f, + f2 +. + f, is dif-
ferentiable on R and (d/dx)(fl + f2 +... + f,) = dfl/dx + df2/dx +. + df,/dx.
Outline of solution It is left to you to provide most of the verifications,
but we note, for example, that in (a), if n = 1, then 5" - 1 = 5 - 1 = 4,
which is indeed divisible by 4. Furthermore, if n = 6, then 5" - 1 =
56 - 1 = 15,625 - 1 = 15,624, which again is divisible by 4. In (b) we
observe that, for n = 10, the sum 1 + 2 + 3 +.. + 10 equals 55, while
the formula [n(n + 1)]/2 also equals 55 when 10 is substituted for n. If
n = 100, then you can verify that both quantities equal 5,050. In (c), if
n = 5, then 4" = 45 = 1,024 > 625 = j4, as claimed. Note that statement
(c) says nothing about the inequality if n = 1,2, 3, or 4. You should try
the inequality in some of these cases as well, keeping in mind, however,
that none of these can serve as a counterexample to (c). As an illus-
tration of (d), we may let n = 5 and consider the functions L(x) = xi
for i = 1, 2, 3, 4, 5. For this specific situation the theorem asserts that
(d/dx)(x + x2 + x3 + x4 + x5) = 1 + 2x + 3x2 + 4x3 + 5x4, a result that,
although laborious to derive from the definition of derivative, is of a
type familiar to every calculus student. 0What do the statements in Example 1 have in common? Compared, say,
to the trigonometric identity "cos 2x = 2 cos2 x - 1 for all x E R," or the
theorem of set theory "A n (B u C) = (A n B) u (A n C) for all sets A, B,
and C," what distinguishes these statements? The answer lies in the nature
of the particular cases used to test the truth of the statements. Choosing
a special case of any of these statements involves choosing a positive integer
n. The reason for this, in turn, is that each of statements (a), (b), and (d)
contains the quantification "for all positive integers n," in symbols (Vn E N).