Bridge to Abstract Mathematics: Mathematical Proof and Structures

186 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5

least one positive integer no, then it is true for infinitely many positive

integers; specifically it is true for at least all positive integers m 2 no.

In Chapter 10 we will deal with other forms of the induction principle,

as well as with "definition by induction," in the context of a development

of the number system of positive integers.

Exercises

1. Use induction to prove parts (a) through (d) of Example 1, that is, prove that
   if n E N, then:
   (a) 4 divides 5" - 1
   (c) 4" > n4, if n 2 5

(b) z=, k = [n(n + 1)]/2

(d) (d/dx)[x; = 1 fk] = x; = 1 (dfddx)

2. Prove, by induction, that for all positive integers n:
   (a) z;= i2 = [n(n + 1)(2n + l)]/6 (b) CI; = k3 = 4(n4 + 2n3 + n2)
   (c) z= j4 = $2(n4 + (3)n3 + ($)n2 - (116))
   3. Use induction to prove that for all positive integers n;
   (a) x= l/j(j + 1) = n/(n + 1)
   *(b) g=, k(k + 1) = [n(n + l)(n + 2)]/3
   (c) z=l (3k2 - 3k + 1)= n3
   (d) 1 +2+4+-.+2"-'=2"- 1


3. Use either an induction argument, or a noninduction proof that employs pre-
   viously noted summation formulas, to prove that for all positive integers n:
   (a) E=,(2k) = n(n + 1)
   (b) 5 + 10 + 15 + ... + 5n = [5n(n + 1)]/2
   (c) Z=,(4k-3)=2n2-n
   :(d) z;= (3k - 2) = (3)n2 - (4)n


4. (a) Use induction, together with the facts cos (x + y) = cos x cos y - sin x sin y
   and cos (n) = - 1, to prove that cos (nn) = (- 1)" for all n E N.
   (b) Suppose a real-valued function f having domain R has the property
   f (x + T) = f (x) for all x E R. Use induction to prove that f(x + nT) = f(x) for
   all x E R and n E N.
   (c) Prove by induction that sin (2i - 1)x = (1 - cos 2nx)/2 sin x, whenever
   x is not an integral multiple of x.


5. (a) Assuming the truth of the triangle inequality, Ix + yl I 1x1 + lyl for all x,
   y r R, prove by induction on n the generalized triangle inequality, if x,, x2,... ,
   xn E R, where n is a positive integer, then IE=, xkl s xi=, Ixkl.
   (b) Suppose it is known that if lim,,, f (x) and lim,,, g(x) both exist, then
   lim,,,( f + g)(x) exists and equals lim,,, f (x) + lim,,, g(x) (i.e., the limit of a sum
   is the sum of the limits, provided both limits exist). Prove by induction that if
   fl(x), f2(x),... , f,(x) are n functions such that lim,,, fix) exists for each i =
   1,2,... , n, then lim,,, (z=, fdx)) exists and equals lim,,, fdx).