Understand · explore · practise
Prove statements by checking every possible case and disprove universal claims with valid counterexamples. Explore parity, remainders and common errors in proof.
Before you startInteger arithmetic and algebraic manipulation
01 / Every possible case
Proof by exhaustion checks every possibility. If the domain is finite, list all values and verify the claim for each one. State why nothing has been left out.
Claim: if n is an integer with 1 ≤ n ≤ 5, then n² + n is divisible by 2.
n: 1, 2, 3, 4, 5
n² + n: 2, 6, 12, 20, 30
All five values are even, and these are all the integers in the stated interval. That proves this finite claim. It does not, by itself, prove the statement for every integer.
For every integer n, use a general argument instead: n² + n = n(n + 1), and one of two consecutive integers is even.
02 / Two exhaustive cases
Every integer n is either even or odd. These two cases exhaust the integers, including zero and negative integers.
Even: n = 2k ⇒ n² = 4k²
Odd: n = 2k + 1
⇒ n² = 4k(k + 1) + 1
Here k is an integer. Thus every integer square has remainder 0 or 1 on division by 4. No integer square has remainder 2 or 3.
These are algebraic families covering all integers, not just two numerical examples.
n is even → n = 2k
Its square is 4 times the integer k².
n is odd → n = 2k + 1
Its square is 4 times k(k + 1), plus 1.
So n² has remainder 0 or 1
Every integer belongs to one of the two cases.
Pause, replay or seek freely. The notes explain the same idea and stay in view.
03 / Three exhaustive cases
Every integer is one of 3k, 3k + 1 or 3k − 1 for an integer k. The last case represents remainder 2 using a more convenient −1.
(3k)³ = 9(3k³)
(3k + 1)³ = 9(3k³ + 3k² + k) + 1
(3k − 1)³ = 9(3k³ − 3k² + k) − 1
So every integer cube is a multiple of 9, one above a multiple of 9, or one below a multiple of 9. In ordinary non-negative remainder notation, the possible remainders are 0, 1 and 8.
The coefficients inside each bracket are integers, which is what makes each first term a multiple of 9.
04 / One counterexample
To disprove “every value in this domain has this property”, find one value in that domain for which the property fails.
For example, n² + n + 5 is not prime for every non-negative integer n: at n = 4 it equals 25 = 5 × 5. The earlier prime values do not rescue the universal claim.
Use the tester to distinguish three outcomes: a valid counterexample, a passing example, and a value outside the claim’s domain. A passing example never proves a universal claim.
n² + n + 5 is prime for every non-negative integer n.
n = 0: n² + n + 5 = 5
5 is prime. This is a passing example, not a proof for every non-negative integer.
05 / Faulty arguments
“The answer is true for 100 values” is evidence for a pattern, not proof over an infinite domain. “I cannot find a counterexample” is not proof either.
From x(x − 1) = 0, dividing by x loses the legitimate solution x = 0. Split into x = 0 and x ≠ 0, or use the zero-product rule. Any step involving division needs a non-zero divisor.
From −2 < 1, multiplying by −1 gives 2 > −1. The direction reverses. If a multiplier’s sign is unknown, split into positive, negative and zero cases as appropriate.
x = −2 implies x² = 4, but x² = 4 does not imply x = −2: x = 2 also works. An implication is not automatically an equivalence.
Starting “suppose (x − y)² ≥ 0” uses a known fact. Starting “suppose the inequality we want is true” cannot establish it unless you explicitly demonstrate an equivalent known statement and justify reversing every step.
06 / Your turn
A counterexample must meet every condition in the claim. For a proof, explain why the cases exhaust the domain.
Prove n² > n for every integer n with 2 ≤ n ≤ 5 by exhaustion.
List all four permitted integers.
n = 2: 4 > 2
n = 3: 9 > 3
n = 4: 16 > 4
n = 5: 25 > 5
These are all integers in the stated domain, so the finite claim is proved.
Disprove “x² > x for every positive real x”.
Try a number between 0 and 1.
x = 1/2: x² = 1/4 < 1/2
The value is positive and the claimed inequality fails, so it is a valid counterexample. x = 0 would be outside this domain.
A student uses n = 1/2 to disprove “n² − n is even for every integer n”. Explain the error and prove the claim.
1/2 is not an integer. Factor n² − n.
n² − n = n(n − 1)
The factors are consecutive integers, so one is even. Their product is even. The student’s proposed input is outside the domain.
Disprove “n² + n + 5 is prime for all non-negative integers n”.
Try n = 4.
4² + 4 + 5 = 25 = 5 × 5
4 lies in the domain, and 25 is composite. One such case is sufficient.
Prove n² and n have the same parity for every integer n.
Consider n = 2k and n = 2k + 1.
n = 2k ⇒ n² = 2(2k²), even.
n = 2k + 1 ⇒ n² = 2(2k² + 2k) + 1, odd.
Every integer is even or odd, so all cases are covered.
Can an integer square equal 4m + 3 for an integer m? Justify your answer.
Use the remainder of a square on division by 4.
No. The exhaustive even/odd argument shows every integer square has remainder 0 or 1 on division by 4, whereas 4m + 3 has remainder 3.
Prove that an integer cube cannot have remainder 4 on division by 9.
Use n = 3k, 3k + 1 or 3k − 1.
The expansions in the three cases give a multiple of 9, a multiple plus 1, or a multiple minus 1. These have remainders 0, 1 and 8. The cases exhaust the integers, and none has remainder 4.
A student claims √(x²) = x for every real x. Give a counterexample and the correct identity.
The square root symbol denotes the non-negative root.
x = −3: √(x²) = √9 = 3 ≠ −3
Correct identity: √(x²) = |x|.
07 / Recap
Section 1 of 7 · Every possible case