]> No Title

""mcs“ —2015/5/18 —1:43 — page 14 —#22

14 Chapter 1 What is a Proo.7

1.6.1 Method #1: Prove Each Statement Implies the Other

The statement P IFF Q"" is equivalent to the two statements P IMPLIES Q“ and "" Q IMPLIES P So you can prove an ""iff“ by proving two implications:

1. Write, ""We prove P implies Q and vice‐versa.'“

2. Write, ""First, we show P implies Q Do this by one of the methods in Section

3. Write, ""Now, we show Q implies P Again, do this by one of the methods in Section

1.6.2 Method #2: Construct a Chain of Iffs

In order to prove that P is true iff Q is true:

1. Write, ""We construct a chain of if‐and‐only‐if implications.“

2. Prove P is equivalent to a second statement which is equivalent to a third statement and so forth until you reach Q.

This method sometimes requires more ingenuity than the first, but the result can be a short, elegant proof.

Example

The standard deviation of a sequence of values x1; x2, . . . , xn is defined to be:

(x1-μ)2+(x2-μ)2++(xn-μ)2n (1.3)

where μ is the average or mean of the values:

μx1+x2+...+xnn

Theorem 1.6.1. The standard deviation of a sequence of values x1, . . . , xn is zero iff all the values are equal to the mean.

For example, the standard deviation of test scores is zero if and only if everyone scored exactly the class average.

Proo. We construct a chain of ""iff“ implications, starting with the statement that the standard deviation () is zero:

(x1-μ)2+(x2-μ)2++(xn-μ)2n=0. (1.4)