]> No Title

""mcs“ —2015/5/18 —1:43 — page 15 —#23

1.7. Proof by Cases 15

Now since zero is the only number whose square root is zero, equation () holds iff

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

Squares of real numbers are always nonnegative, so every term on the left hand side of equation () is nonnegative. This means that () holds iff

Every term on the left hand side of () is zero. (1.6) But aterm (xi-μ)2 is zero iff xi=μ, so () is true iff

Every xi equals the mean.

1.7 Proof by Cases

Breaking a complicated proof into cases and proving each case separately is a com‐ mon, useful proof strategy. Here's an amusing example.

Let's agree that given any two people, either they have met or not. If every pair of people in a group has met, we'll call the group a club. If every pair of people in a group has not met, we'll call it a group of strangers.

Theorem. Every collection of 6 people includes a club of 3 people or a group of 3 strangers.

Proo. The proof is by case analysis. Let x denote one of the six people. There are two cases:

1. Among 5 other people besides x, at least 3 have met x. 2. Among the 5 other people, at least 3 have not met x.

Now, we have to be sure that at least one of these two cases must hold, but that's easy: we've split the 5 people into two groups, those who have shaken hands with x and those who have not, so one of the groups must have at least half the people. Case 1: Suppose that at least 3 people did meet x.

This case splits into two subcases:

5Describing your approach at the outset helps orient the reader.

6Part of a case analysis argument is showing that you've covered all the cases. This is often obvious, because the two cases are of the form P“ and ""not P However, the situation above is not stated quite so simply.