Complete cases and counterexamples
| English | Français |
|---|---|
| proof by exhaustion/pruːf baɪ eɡˈzɔːstʃn/ | proof by exhaustion |
When do three cases cover every integer?
- Testing a thousand integers may miss the next counterexample. A complete list of possible remainders can instead settle every integer.
- This lesson studies proof by exhaustion 穷举证明: A proof that checks every possibility in a finite, complete set of cases.
Choose the mathematical structure
- Write n=3k, 3k+1 or 3k+2 for integer k. These are all possible remainders on division by 3, including negative integers. Evaluate the expression in each case. One counterexample disproves a universal claim; examples supporting a claim do not prove it.
- State the allowed inputs and units before calculating. An equation should express the relationship, not just record a calculator entry.
Which description correctly defines proof by exhaustion?
A proof that checks every possibility in a finite, complete set of cases.
Work through a checked case
- Check the result against the starting quantities. Substitute into the original relation, or compare the graph and numerical answer where appropriate.
For n=3k, n²=9k² is divisible by 3. For n=3k+1, n²=3(3k²+2k)+1. For n=3k+2, n²=3(3k²+4k+1)+1. Thus an integer square has remainder 0 or 1, never 2. The claim that n²+n+41 is always prime fails at n=41: its value is 1763=41×43.
Complete cases and counterexamples
Write n=3k, 3k+1 or 3k+2 for integer k
Classify each argument and explain the condition that makes it valid or incomplete.
How many remainder cases are needed for division by 3?
The possible remainders are 0,1,2, giving three cases.
Test a tempting shortcut
- A finite sample is not exhaustion unless it contains every possible case. Checking n=0,1,2 alone is not enough: the expressions involving arbitrary integer k justify all integers.
- When a shortcut fails, identify the assumption it breaks. Keep an exact value until the requested final rounding.
If a claim works for the first hundred integers, it has been proved for all integers. This claim is false. Explain which definition or assumption it violates.
What remainder does 8² have on division by 3?
64=3×21+1.
If a claim works for the first hundred integers, it has been proved for all integers.
A finite sample is not exhaustion unless it contains every possible case. Checking n=0,1,2 alone is not enough: the expressions involving arbitrary integer k justify all integers.
Interpret a new situation
- Choose a complete case split, such as parity or remainders. State why no case is missing. For a false universal claim, give a valid input and verify the failure directly.
- A complete solution gives the mathematical result and explains what it means. Check that it is possible in the stated context.
Evaluate n²+n+41 at n=41.
41²+41+41=1763=41×43.
Match each part of a complete solution to its purpose.
An assumption justifies the model; a check tests the result; interpretation connects it to the question.
Use this in your course
- 7357 · A-level · A. Match the target tier and specification before assigning extensions.
- Give the method before the final answer, and use the paper's calculator and formula rules. Review a wrong answer by locating the first invalid step.
A proof that checks every possibility in a finite, complete set of cases. Choose the relationship, show the method, check its assumptions and interpret the result.