Bridge to Abstract Mathematics: Mathematical Proof and Structures

160 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5

prove this, it is sufficient, by Theorem 1, to prove (i) 1 E S and (ii) for

each m E N, if m E S, then (m + 1) E S.

1. Clearly 1 E S, since l2 = 1 = the sum of the "first 1" odd positive
   integers.


2. Let m E S be given. Hence 1 + 3 +... + (2m - 1) = m2. (The as-
   sumption m E S with which step (2) begins in every induction proof
   is often called the induction hypothesis or the inductive assumption.)
   To prove m + 1 E S, we must prove

In the course of the latter proof in turn we must make use of the

induction hypothesis. Note now that

[l + 3 + 5 +. + (2m - I)] + [2(m + 1) - 11

= [l +3+ 5 +-..+(2m- I)] +(2m+ 1)

= m2 + (2m + 1) (We have just used the

induction hypothesis.)

= (m + I)~.

This is precisely what was needed to prove m + 1 E S, so that condition

(ii) is verified and the proof is complete.

EXAMPLE 3 Assume that the product rule for the derivative (fg)'(x) =

f (x)g'(x) + f'(x)g(x) is known. Use this rule to prove that, for all positive

integers n, if f(x) = xn, then f'(x) = nxn-'.

Solution Every student with a calculus background is familiar with this

rule. Since its statement involves the phrase "for all positive integers n,"

it is a candidate for proof by mathematical induction. We begin such

a proof by letting S be the set of those positive integers m for which the

theorem is true: If m is a positive integer, then m E S if and only if

(d/dx)(xm) = mxm- l. To prove S = N, we must prove (1) 1 E S and (2) for

all m E N, if m E S, then m + 1 E S.

1. Clearly 1 E S, since (d/dx)(xl) = dxldx = 1 and lxl - = lxO = x0 = 1.


2. Assume m E S. To prove m + 1 E S, we must show that (d/dx)(xm+ l) =
   (m + l)xm, using the inductive assumption that (d/dx)(xm) = mxm-l.
   Now
   (d/dx)(xm + l) = (d/dx)(xm x)
   = xm(dx/dx) + x[(d/dx)(xm)] (by the product rule)
   = xm(l) + (x)(mxm- l) (by the induction
   hypothesis)
   = xm + mxm
   = (m + l)xm, as desired 0