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

$\mathrm{\left(}{\mathit{x}}_{\mathrm{1}}\mathrm{-}\mathit{\mu }{\mathrm{\right)}}^{\mathrm{2}}\mathrm{+}\mathrm{\left(}{\mathit{x}}_{\mathrm{2}}\mathrm{-}\mathit{\mu }{\mathrm{\right)}}^{\mathrm{2}}\mathrm{+}\mathrm{\text{...}}\mathrm{+}\mathrm{\left(}{\mathit{x}}_{\mathit{n}}\mathrm{-}\mathit{\mu }{\mathrm{\right)}}^{\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{\left(}\mathrm{\right)}$ is nonnegative. This means that $\mathrm{\left(}\mathrm{\right)}$ holds iff

Every term on the left hand side of $\mathrm{\left(}\mathrm{\right)}$ is zero. (1.6) But aterm $\mathrm{\left(}{\mathit{x}}_{\mathit{i}}\mathrm{-}\mathit{\mu }{\mathrm{\right)}}^{\mathrm{2}}$ is zero iff ${\mathit{x}}_{\mathit{i}}\mathrm{=}\mathit{\mu }$, so $\mathrm{\left(}\mathrm{\right)}$ 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:

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.