""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 $\mathrm{(}\mathrm{)}$ holds iff

$\mathrm{(}{\mathit{x}}_{\mathrm{1}}\mathrm{-}\mathit{\mu}{\mathrm{)}}^{\mathrm{2}}\mathrm{+}\mathrm{(}{\mathit{x}}_{\mathrm{2}}\mathrm{-}\mathit{\mu}{\mathrm{)}}^{\mathrm{2}}\mathrm{+}\mathrm{\text{...}}\mathrm{+}\mathrm{(}{\mathit{x}}_{\mathit{n}}\mathrm{-}\mathit{\mu}{\mathrm{)}}^{\mathrm{2}}\mathrm{=}\mathrm{0}$. (1.5)

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

Every term on the left hand side of $\mathrm{(}\mathrm{)}$ is zero. (1.6) But aterm $\mathrm{(}{\mathit{x}}_{\mathit{i}}\mathrm{-}\mathit{\mu}{\mathrm{)}}^{\mathrm{2}}$ is zero iff ${\mathit{x}}_{\mathit{i}}\mathrm{=}\mathit{\mu}$, so $\mathrm{(}\mathrm{)}$ is true iff

Every ${\mathit{x}}_{\mathit{i}}$ equals the mean.

$\mathrm{\blacksquare}$

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 $\mathit{x}$ denote one of the six people. There are two cases:

1. Among 5 other people besides $\mathit{x}$, at least 3 have met $\mathit{x}\mathrm{.}$ 2. Among the 5 other people, at least 3 have not met $\mathit{x}\mathrm{.}$

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 $\mathit{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 $\mathit{x}\mathrm{.}$

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 $\mathit{P}$“ and ""not $\mathit{P}$ However, the situation above is not stated quite so simply.