182 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5
Solution Let S be the truth set ofp(n): x=, (k/2k) = 2 - [(n + 2)/2"]. To
prove S = N, we need only verify (i) and (ii) of Theorem 1.
- 1 E S, since z;=, (k/23 = 112' = 4 = 2 - (3) = 2 - [(1 + 2)/2l].
- Assume m E S. To prove m + 1 E S, we must show that Zm:: (k/2k) =
2 - [((m + 1) + 2)/2"+']. First, we note that we can express
xp.: (k/2S as Cp=, (k/25 + [(m + 1)/2'+ ' 1.
Applying the induction hypothesis, we transform the latter expression
to
[2 - ((m + 2)/2")] + ((m + 1)/2"+')
which equals
Simplifying, we get
[2m'2 - (m + 3)]/2"+', that is, 2 - [((m + 1) + 2)/2'+'], as desired.
0
In the next example of an induction proof we verify a basic property of
summation notation.
EXAMPLE 5 Suppose n is a positive integer and x ,, x2,... , x,, y l, yz ,... , yn
are (2n) real numbers. Prove that z,, (x, + yk) = z=, xk + E,, y,.
proof Let S be the truth set of p(n): z=, (x, + y,) = It=, xk + E=, yk.
We claim S = N. We must verify (i) and (ii) of Theorem 1.- 1 ES, since z=, (xk +yk) =xl +yl =Z=l xk + Y,.
- Assume m E S. To prove m + 1 E S, we musf show
This follows from the string of equations,= [(e k=l xk) + xm+l] + [(e k=l Yk) + ym+l]
m+l m+l
= 1 xk + x y,, as desired.
k=l k=l
You should apply justifications for each of'the preceding steps, noting
especially where the induction hypothesis is used. 0