Mathematical Proof: Exhaustion and Disproof by Counter-Example

A question asks you to prove, by exhaustion, that a property holds for every pair of positive integers $(x, y)$ with $x + y = 11$ and $x < y$. How many cases must you list?

• 5 — the pairs $(1,10), (2,9), (3,8), (4,7), (5,6)$

  Correct. $x < y$ with $x + y = 11$ means $x$ can be at most 5 (at $x = 5.5$ the two would be equal), and $x$ is a positive integer, so $x \in \{1,2,3,4,5\}$ — exactly five cases, each generating one pair via $y = 11 - x$.

• B10 — every ordered pair of positive integers summing to 11

  This counts $x$ from 1 to 10 without applying the condition $x < y$, which was stated specifically to avoid counting each unordered pair twice (once as $(x,y)$ and once as $(y,x)$). The stated inequality is part of the domain, not an afterthought to drop.

• C6 — including the case $x = 5.5, y = 5.5$

  $x$ and $y$ are stated to be positive integers, and 5.5 is not one. The condition $x < y$ excludes equality on its own, but even without it, a non-integer value was never inside the domain the question defined.

• D4 — the pairs $(1,10)$ through $(4,7)$

  This stops one case short: $(5,6)$ satisfies $x + y = 11$ and $x < y$ just as validly as the other four, and $x = 5$ is the largest integer still strictly below $5.5$. A boundary case is still a case.

Traps tested: Case list padded · Domain restriction ignored · Case list left incomplete

Positive integers $a$ and $b$ satisfy $b = a + 4$ and $a + b \leq 14$. Which is the correct, complete list of pairs $(a, b)$ to check in a proof by exhaustion covering every valid pair?

• $(1,5), (2,6), (3,7), (4,8), (5,9)$

  Correct. Substituting $b = a + 4$ into $a + b \leq 14$ gives $2a + 4 \leq 14$, so $a \leq 5$; with $a$ a positive integer, $a \in \{1,2,3,4,5\}$, giving exactly these five pairs. Checking the boundary: $a = 5$ gives $a + b = 5 + 9 = 14$, which does satisfy $\leq 14$, so it correctly belongs in the list.

• B$(5,1), (6,2), (7,3), (8,4), (9,5)$

  This comes from applying the relation backwards, as $b = a - 4$ instead of $b = a + 4$ — the same error a real examiner report documents on a comparable question, where a stated relationship between the variables was applied in the wrong direction and generated an entirely different (and wrong) set of cases from the first line onward.

• C$(1,5), (2,6), (3,7), (4,8)$

  This uses $a < 5$ instead of $a \leq 5$, dropping the boundary pair $(5, 9)$. Checking it directly: $5 + 9 = 14$, which does satisfy $a + b \leq 14$, so it is a valid case that has been left off the list.

• D$(1,5), (2,6), (3,7), (4,8), (5,9), (6,10)$

  The sixth pair fails the stated condition: $6 + 10 = 16$, which is not $\leq 14$. Adding a case outside the stated bound is the same error, in the opposite direction, as leaving one out — the list has to match the domain exactly.

Traps tested: Case defining relation applied backwards · Case list left incomplete · Case list padded

You are asked to disprove the statement "$n^2 + 2n + 3$ is even for every positive integer $n$." You find that $n = 1$ gives $6$ (even) and $n = 2$ gives $11$ (odd). What should you write next?

• State that $n = 2$ is a counter-example: $2^2 + 2(2) + 3 = 11$, which is odd, so the statement is disproved. No further values need checking.

  Correct. One failing case is sufficient to disprove a "for every" claim, and the case has been exhibited with the working shown, not just asserted. Nothing further is required or rewarded.

• BCheck $n = 3, 4$ and $5$ as well, to build a stronger case before concluding

  The claim was already disproved at $n = 2$. Continuing to test further values is the exact documented pattern of real scripts finding "far more than necessary" — it costs time without adding any credit the single counter-example did not already earn.

• CDiscard $n = 2$ as an exception and conclude the statement is true for all other values of $n$

  This rewrites the claim into a different, weaker one the question never asked. "For every positive integer n" includes n = 2; a single failure inside that stated domain disproves the statement as given, and there is no scheme under which a counter-example gets excluded from the domain it was found in.

• DGo back and re-derive the general formula for $n^2 + 2n + 3$ algebraically to confirm the pattern before committing to an answer

  A specific, checked counter-example is already a complete disproof; a general algebraic derivation afterwards answers a stronger question that was never asked and spends time the single exhibited case did not need.

Traps tested: Counter example count inflated · Counter example dismissed as exception · Unnecessary second method added

A claim is written as "$g(n)$ holds for all positive integers $n$." Why can this claim be disproved by one failing value of $n$, while proving it true needs every value checked?

• It is really the statement $g(1)$ AND $g(2)$ AND $g(3)$ AND … all at once; an AND is false if even one part is false, but is true only if every part is true.

  Correct — this is the structural fact the whole topic rests on. A "for all" claim is a conjunction over every case in its domain; a conjunction needs every part true to be true (which is why proving it needs every case checked, when that's possible at all) but needs only one part false to be false (which is why disproving it never needs more than one case).

• BMathematicians allow a lower standard of evidence for disproving a claim than for proving one, as a matter of convention

  This isn't a convention or a courtesy — it follows directly from what "for all" means. A conjunction with one false part is false regardless of any agreed standard; there is no leniency being granted, only a structural fact about AND being used.

• CDisproving is easier because it only involves arithmetic, while proving requires algebra

  Both worked examples in this lesson use only arithmetic — exhaustion checks specific numerical cases, and the counter-example search tests specific numerical values of n. The asymmetry is about how many cases each task needs to establish, not about which kind of calculation is involved.

• DIt can't — disproving a "for all" claim genuinely does require checking every value, the same as proving one

  This denies the premise the whole topic and the spec's own guidance are built on. The spec's worked example for disproof — "n² − n + 1 is a prime number for all values of n" — is disproved with a single value of n, and June 2019's examiner report states the underlying rule explicitly: only one counter-example is required.

Traps tested: Asymmetry treated as convention · Asymmetry attributed to calculation type · Disproof workload equated with proof

Which of these claims can be proved by exhaustion, as the technique is defined on this paper?

• "The product $xy$ is even, for every pair of positive integers $x, y$ with $x + y = 8$ and $x < y$"

  Correct. $x + y = 8$ with $x < y$ restricts $x$ to a small, explicitly bounded set of positive integers (x can be at most 3, since x = 4 would force x = y). A finite, listable domain is exactly what exhaustion needs.

• B"$n^2 + n$ is even, for every positive integer $n$"

  This domain is every positive integer with no upper bound — infinite, and therefore not listable. It happens to be true (n² + n = n(n+1), a product of consecutive integers, always even), but exhaustion specifically cannot be the method that proves it here, whatever other technique might.

• C"$3^x > 100$, for every real number $x > 4$"

  The domain here is every real number greater than 4 — not just infinite but uncountable, with no way to list even a first case, let alone all of them. This is even further from exhaustion's requirements than an unbounded integer domain.

• D"There exists a positive integer $n$ for which $n^2 - n + 5$ is not prime"

  This is an "there exists" claim, not a "for all" claim — it is disproved (or proved) by finding one example, which is a counter-example search, not exhaustion. Exhaustion is specifically the technique for proving a "for all" claim true over a finite domain.

Traps tested: Exhaustion attempted on an unbounded domain · Exhaustion confused with existence claim