Back to the on-screen lesson ·
Splitting a claim on parity, sign or remainder, checking that the split leaves nothing out, and refuting a universal claim with one exhibited object.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to choose a split from the shape of the obstacle, check that the cases cover every object including the boundary, prove the claim in each case using that case's assumption, and finish by saying the split was exhaustive. You will also be able to refute a universal claim by exhibiting one counterexample, and say why a list of confirming cases is not partial progress towards a proof.
You have three ways of proving an implication and one way of writing down what would refute a universal claim: lesson 5's negation, which turns $\forall x\, P(x)$ into $\exists x\, \neg P(x)$. This lesson spends that negation, and adds the technique for claims whose objects come in kinds.
A split into cases is exhaustive when every object of the right kind falls into at least one case; the cases may overlap, and usually it is tidier if they do not. A counterexample to $\forall x\, P(x)$ is a single $x$ with $\neg P(x)$. Without loss of generality marks a case that the argument for another case covers unchanged, by symmetry.
Some claims resist a single argument because the objects they are about come in kinds. $n^2 + n$ is even for every integer $n$, and the reason is different depending on whether $n$ is even or odd. So do both, separately, and say that the two kinds account for every integer.
The technique has exactly one hazard, and it is the last line. A split is itself a claim — every object falls into one of these cases — and it is not self-evident. Splitting the reals into $x > 0$ and $x < 0$ leaves out zero. Splitting the integers into primes and composites leaves out $1$ and $0$. Nobody writes that split down intending to cheat; it happens because the missing object is the least interesting one, which is precisely why nothing draws attention to it.
So a proof by cases has four parts: state the split, argue each case, and say the split was exhaustive. Three parts to write and one to check.
The mirror image of the technique is refutation. To refute $\forall x\, P(x)$ you need one $x$ with $\neg P(x)$ — not an argument, not a pattern, just one object, exhibited. Finding it is a search rather than a proof, and once found it settles the matter completely and permanently. That asymmetry is worth pausing on: a universal claim takes an argument to establish and one example to destroy, and an existential claim is the other way round.
Another way: steps
To prove by cases:
Another way: example
For $n^3 - n$ divisible by three, split on the remainder of $n$ on division by three: $0$, $1$ or $2$, which is exhaustive because those are the only remainders there are. Three cases rather than two, and the third is not optional even though it looks like the second.
| The obstacle | The split | Cases |
|---|---|---|
| parity of an integer | even or odd | $2$ |
| an absolute value | the argument's sign | $2$ |
| divisibility by $m$ | the remainder | $m$ |
| two quantities compared | $a \le b$ or $a > b$ | $2$ |
| a maximum or a minimum | which one attains it | as many as there are |
Two cases is usual, three is common, and more than four is a sign that the split is the wrong one. When two cases have the same argument with the names exchanged, you may do one and say without loss of generality — but only when the exchange really is a symmetry of the whole claim, and it is worth saying out loud which symmetry, because the phrase is also where a gap gets buried.
A split with a gap. $x > 0$ or $x < 0$ misses zero; primes or composites misses $1$; $a < b$ or $a > b$ misses equality. Check the boundary every time.
Proving one case and stopping. A claim proved for even $n$ is a claim about even $n$.
Using the wrong case's assumption. Inside the case $n = 2k+1$, $n$ is odd, and writing $n = 2k$ three lines later is a slip nothing in the algebra will catch.
Offering examples as a refutation of an existence claim. A counterexample refutes a universal claim. To refute $\exists x\, P(x)$ you need an argument covering every $x$, and failing to find one is not that argument.
A claim checked at $n = 1$ through $n = 40$ and found true is not forty per cent proved, or ninety, or any fraction at all. $n^2 + n + 41$ is prime for $n = 0$ to $39$ and composite at $n = 40$; the forty successes were never evidence about the forty-first, because nothing connected them. What would connect them is an argument that carries each case to the next — which is induction, and is the next lesson.
Claim: $|x| \ge x$ for every real $x$. The absolute value is defined in two cases, so split the same way: $x \ge 0$ and $x < 0$.
Take the split from the definition.
If $x \ge 0$ then $|x| = x$, and $x \ge x$ holds with equality.
The first case is nearly trivial and is still a case.
If $x < 0$ then $|x| = -x$, which is positive while $x$ is negative, so $|x| > x$. Every real is in one case or the other, so the inequality holds throughout.
The last line is what finishes it.
Claim: $2^n - 1$ is prime for every $n \ge 2$. Test upwards: $3$, $7$, $31$ — three primes in a row.
Three confirmations, no argument.
At $n = 4$: $2^4 - 1 = 15 = 3 \times 5$. The claim is false, and that is the whole refutation — one number, exhibited.
One object settles a universal claim.
Notice how cheap the refutation was and how expensive a proof would have been. That asymmetry is why a conjecture is tested numerically first: the cheap outcome is checked before the expensive one is attempted.
Search before you argue.
The obstacle is parity, so split on it: $n$ even, or $n$ odd. Those two cover every integer.
State the split and check it is exhaustive.
If $n = 2k$ then $n(n+1) = 2k(2k+1)$, which is twice an integer.
First case.
If $n = 2k+1$ then $n + 1 = 2k + 2 = 2(k+1)$, so $n(n+1) = 2(k+1)(2k+1)$, also twice an integer. Both cases give an even number and the split is exhaustive, so the claim holds. Notice the real content: of any two consecutive integers, one is even — which is a fact worth remembering in its own right.
Here are the four lines of a proof, by cases, that $n^2 + n$ is even for every integer $n$. Put them in order.
Number the steps in order (write the number in the box):
The claim '$2^n - 1$ is prime for every $n \ge 2$' is false. What is the smallest counterexample?
Answer:
Show that $n^2 + n$ is even for every integer $n$ by filling in both cases. Give the remainder each case leaves on division by $2$.
| Remainder of $n^2 + n$ on division by $2$ | |
|---|---|
| $n$ even, so $n = 2k$ | |
| $n$ odd, so $n = 2k + 1$ |
For which real numbers $x$ does $|x - 9| = x - 9$ hold? Give the set.
This task has no paper form; do it on a device.
Somebody proves that $n^3 - n$ is divisible by $3$ by splitting into two cases: $n$ leaves remainder $0$ or $1$ on division by $3$, and $n$ leaves remainder $2$. Do the cases cover everything?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Here are the four lines of a proof, by cases, that $|x| \ge x$ for every real number $x$. Put them in order.
Number the steps in order (write the number in the box):
You can split a claim into exhaustive cases, prove each and say so, and refute a universal claim with one example. Say in your own words where a split most often leaves a gap, and why forty confirming cases are no evidence about the forty-first. Next: the technique that does connect each case to the next.
10. Your turn: prove that $n(n+1)$ is even for every integer $n$, step 3