Proof Writing for Olympiads | Induction, Contradiction and the Extremal Principle

From a Numerical Pattern to a Proof: Quantifiers, Counterexamples and General Claims

A pattern is often where mathematical discovery begins. It is not where a universal claim ends.

If the first ten cases work, the eleventh may fail. If a calculator shows the same behaviour across a wide range, the behaviour may still break outside the window. If a statement looks true for positive integers, it may fail for zero, negative integers, rational numbers or real numbers.

The move from pattern to proof requires four controls:

1. state the claim precisely;
2. state the domain;
3. identify the quantifier;
4. use an argument strong enough to cover every case the claim includes.

1. Start with the quantifier

Mathematical statements often hide words such as all, some, there exists, for every, at least one and exactly one.

Compare:

• For every integer (n), (n^2+n) is even.
• There exists an integer (n) such that (n^2+n) is even.

The first is universal. The second is existential. A single example can prove the second. It cannot prove the first.

2. Example evidence is not universal proof

Check:

[ 1^2+1=2,quad 2^2+2=6,quad 3^2+3=12,quad 4^2+4=20. ]

The outputs are even. This is good evidence for a conjecture. But the proof should explain why the structure forces evenness for every integer (n).

Factor:

[ n^2+n=n(n+1). ]

Two consecutive integers cannot both be odd. One of (n) and (n+1) is even. Therefore their product is even. The argument covers every integer.

3. The domain is part of the claim

Consider:

“For every number (x), (x^2ge x).”

For integers, this is true. For real numbers, it is false. Take (x=rac12):

[ x^2=rac14<rac12=x. ]

The same sentence changes truth value when the domain changes.

A proof cannot be judged until the domain is explicit.

4. Counterexamples disprove universal claims efficiently

A universal statement has the form “for every object in the domain, property (P) holds.” To disprove it, one valid counterexample is enough.

Claim: “Every prime number is odd.”

Counterexample: (2) is prime and even.

The claim is false.

Do not produce a hundred odd primes. A single counterexample settles the universal statement.

5. Counterexamples must belong to the domain

If the claim is “every positive integer has property (P)”, a negative number cannot disprove it. If the claim concerns triangles, a quadrilateral is irrelevant. If the claim is about non-zero real numbers, zero cannot be used as a counterexample.

A good counterexample attacks the exact statement.

6. Conjecture from a pattern

Compute:

[ 1=1^2 ]

[ 1+3=4=2^2 ]

[ 1+3+5=9=3^2 ]

[ 1+3+5+7=16=4^2. ]

A natural conjecture is:

[ 1+3+5+cdots +(2n-1)=n^2 ]

for every positive integer (n).

The examples reveal the pattern. Now the learner needs proof.

7. Proof by induction

Base case: for (n=1), the left side is (1) and the right side is (1^2=1).

Inductive hypothesis: assume for some positive integer (k) that:

[ 1+3+cdots +(2k-1)=k^2. ]

Inductive step: for (k+1), add the next odd number (2k+1):

[ 1+3+cdots +(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2. ]

Therefore the statement holds for every positive integer (n).

The proof works because the case (k+1) is connected to the assumed case (k).

8. What induction is not

Checking (n=1,2,3,4,5) is not induction. Writing “assume true for (n=k)” and then manipulating the (k+1) case without using that assumption is also incomplete.

Induction requires the bridge from one case to the next.

9. Direct proof from definitions

Claim: the sum of two even integers is even.

Let the integers be (2a) and (2b), where (a,binmathbb Z). Their sum is:

[ 2a+2b=2(a+b). ]

Because (a+b) is an integer, the sum has the form (2k) for an integer (k). Therefore it is even.

The proof begins with the definition of evenness and ends by recovering the same definition.

10. Direct proof with divisibility

Claim: if an integer is divisible by (6), then it is divisible by (3).

If (n) is divisible by (6), then (n=6k) for some integer (k). Rewrite:

[ n=3(2k). ]

Since (2k) is an integer, (n) is divisible by (3).

11. Converse is not automatic

Original statement:

“If (n) is divisible by (6), then (n) is divisible by (3).”

Converse:

“If (n) is divisible by (3), then (n) is divisible by (6).”

The converse is false. (n=9) is divisible by (3) but not (6).

Many proof errors come from silently replacing a statement by its converse.

12. Contrapositive can be easier than direct proof

Claim: if (n^2) is even, then (n) is even.

The direct route can be awkward. Prove the contrapositive:

“If (n) is odd, then (n^2) is odd.”

Let (n=2k+1). Then:

[ n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1, ]

which is odd. Therefore the contrapositive is true, so the original statement is true.

13. Proof by contradiction

A contradiction proof assumes the negation of the desired result and shows that assumption cannot coexist with known facts.

Classic example: prove (sqrt2) is irrational.

Assume instead that:

[ sqrt2=rac{a}{b} ]

for integers (a,b) with no common factor and (b e0).

Squaring gives:

[ 2=rac{a^2}{b^2}, ]

so:

[ a^2=2b^2. ]

Thus (a^2) is even, hence (a) is even. Let (a=2k). Then:

[ 4k^2=2b^2, ]

so:

[ b^2=2k^2. ]

Thus (b) is also even. But then (a) and (b) share a factor of (2), contradicting the assumption that the fraction was in lowest terms. Therefore (sqrt2) is irrational.

14. Contradiction must contradict something real

It is not enough to reach a surprising expression. The contradiction must violate an assumption, definition or established fact.

“This looks impossible” is not a contradiction.

15. Proof by cases

Claim: for every integer (n), (n(n+1)) is even.

One direct proof uses consecutive integers. Another route is proof by cases.

Case 1: (n) is even. Then (n(n+1)) is even because it contains the even factor (n).

Case 2: (n) is odd. Then (n+1) is even, so (n(n+1)) is even.

The cases cover all integers. Therefore the product is always even.

16. Case splits must be exhaustive

A proof by cases fails if the cases leave possibilities uncovered. For real numbers, splitting into “positive” and “negative” misses zero. For integers, splitting into “even” and “odd” is exhaustive.

17. The extremal principle

Sometimes choosing a largest, smallest, earliest or nearest object forces structure.

Example: among a finite set of positive integers, choose the smallest element. Any operation that supposedly produces a smaller positive element can contradict minimality.

Extremal arguments are powerful because the extreme object has fewer possibilities than a generic object.

18. Minimal counterexample method

Suppose a statement is believed true for all positive integers. Assume it is false and choose the smallest positive integer (n) for which it fails.

If the structure of the problem lets you produce a smaller counterexample from (n), then the choice of (n) as the smallest failure is contradicted. This proves no counterexample exists.

19. Numerical pattern that fails later

Consider:

[ n^2+n+41. ]

For many small non-negative integers (n), the output is prime. It is tempting to conjecture that the expression always produces a prime number.

But at (n=41):

[ 41^2+41+41=41(41+2)=41cdot43, ]

which is composite.

The long successful pattern was evidence, not proof.

20. Numerical pattern that points toward a proof

Consider:

[ 1^3+2^3+cdots+n^3. ]

Compute small cases:

[ 1=1 ]

[ 1+8=9 ]

[ 1+8+27=36 ]

[ 1+8+27+64=100. ]

These are:

[ 1^2, 3^2, 6^2, 10^2. ]

The square roots are triangular numbers. A plausible conjecture is:

[ 1^3+2^3+cdots+n^3=left(rac{n(n+1)}2 ight)^2. ]

The pattern helps discover the statement. A proof is still required.

21. General claim from algebraic structure

Claim: the square of every odd integer is odd.

Let:

[ n=2k+1. ]

Then:

[ n^2=4k^2+4k+1=2(2k^2+2k)+1. ]

This has the form (2m+1), so it is odd.

22. General claim that is false because of a boundary case

Claim: “If (ab=ac), then (b=c).”

This is false without a condition on (a). Let (a=0), (b=1), (c=2). Then:

[ ab=0=ac ]

but (b e c).

The corrected statement is:

“If (ab=ac) and (a e0), then (b=c).”

The missing condition is the mathematics.

23. The role of definitions

Many proof problems become easier when the learner asks, “What does this word mean mathematically?”

Examples:

• even integer → (2k);
• odd integer → (2k+1);
• divisible by (m) → (mk);
• one-to-one function → equal outputs imply equal inputs;
• subset → every element of one set belongs to the other;
• prime → positive integer greater than (1) with exactly two positive divisors.

A definition is not background information. It is often the first move of the proof.

24. Quantifier order changes the statement

Compare:

[ orall xinmathbb R, exists yinmathbb R ext{ such that }y>x ]

and:

[ exists yinmathbb R, orall xinmathbb R, y>x. ]

The first is true. Given any (x), choose (y=x+1).

The second is false. No real number is greater than every real number.

The same symbols appear. Their order changes the claim.

25. Negating quantified statements

To disprove or use contradiction, learners need correct negation.

The negation of:

“For every (x), (P(x)) holds”

is:

“There exists an (x) such that (P(x)) does not hold.”

The negation of:

“There exists an (x) such that (P(x)) holds”

is:

“For every (x), (P(x)) does not hold.”

This is why one counterexample destroys a universal statement.

26. Existence proof versus construction

Sometimes proving that an object exists means constructing one.

Claim: there exist two irrational numbers (a,b) such that (a^b) is rational.

A famous proof splits into cases using:

[ (sqrt2)^{sqrt2}. ]

If this number is rational, take (a=b=sqrt2). If it is irrational, let:

[ a=(sqrt2)^{sqrt2},qquad b=sqrt2. ]

Then:

[ a^b=left((sqrt2)^{sqrt2} ight)^{sqrt2}=(sqrt2)^2=2, ]

which is rational.

The proof establishes existence without deciding which branch holds.

27. Uniqueness needs its own argument

Showing that a solution exists does not show it is unique.

If a problem asks for exactly one object, the proof often has two parts:

1. existence: show at least one object works;
2. uniqueness: show no two different objects can both work.

28. A proof can be correct but poorly scoped

Suppose the task is to prove a result for every real number, but the proof assumes (x>0) without justification. The argument may be correct on positive reals and still fail the stated problem.

Scope must stay visible.

29. A diagram is evidence unless its properties are established

A geometry diagram can suggest equal lengths or angles that are not given. Never prove from appearance alone.

Use the diagram to discover a route. Use stated conditions and theorems to justify the route.

30. A calculator is evidence unless the claim is numerical

A calculator can test cases, approximate roots and generate conjectures. It cannot prove a universal integer identity merely by checking many values.

Technology is excellent for exploration. The proof must match the logical size of the claim.

31. Example: prove the sum of consecutive integers

Claim: the sum of three consecutive integers is divisible by (3).

Let the integers be:

[ n, n+1, n+2. ]

The sum is:

[ 3n+3=3(n+1), ]

which is divisible by (3).

32. Example: false generalisation from even cases

A learner observes:

[ 2^2-2=2,quad4^2-4=12,quad6^2-6=30 ]

and conjectures that (n^2-n) is even for every even integer (n).

The conjecture is true but unnecessarily narrow. In fact:

[ n^2-n=n(n-1), ]

a product of consecutive integers, so it is even for every integer (n), not just even integers.

Proof can reveal that the pattern is stronger than the first conjecture.

33. Example: find the weakest sufficient claim

If a theorem is true under a broad domain, do not add assumptions merely because they appeared in the examples.

Mathematical maturity includes removing unnecessary conditions.

34. Proof debugging: first invalid inference

Read proofs line by line. A proof can contain true statements connected by an invalid inference.

Example:

“All squares are non-negative. (x^2) is non-negative. Therefore (x) is non-negative.”

The conclusion does not follow. (x=-3) has (x^2=9ge0). The first two statements are true; the implication is invalid.

35. Proof debugging: assuming the conclusion

A circular proof uses the desired conclusion as part of its justification.

If the task is to prove (A), writing “Assume (A), therefore…” proves nothing unless the method is explicitly contradiction and the assumption is the negation of the claim.

36. Proof debugging: proving the converse

If asked to prove (PRightarrow Q), proving (QRightarrow P) is a different statement.

Always write the direction before starting.

37. Proof debugging: one example mistaken for existence of all

An example can prove an existential statement. It cannot usually prove a universal one.

Ask: what is the quantifier?

38. Proof debugging: algebra valid only on part of the domain

Dividing by an expression containing the variable can assume that expression is non-zero. Taking square roots can lose sign branches. Squaring can add candidates. Proof algebra needs the same domain discipline as equation solving.

39. A conjecture worksheet should have five fields

40. Fresh conjecture 1

Calculate (n^2-n) for several integers. Conjecture a divisibility property. Then prove it.

Solution structure:

[ n^2-n=n(n-1), ]

a product of consecutive integers, hence even.

41. Fresh conjecture 2

Calculate:

[ 1+2+cdots+n ]

for small (n). Conjecture:

[ 1+2+cdots+n=rac{n(n+1)}2. ]

Then prove the formula by induction or a pairing argument.

42. Pairing proof

Write:

[ S=1+2+cdots +(n-1)+n. ]

Reverse:

[ S=n+(n-1)+cdots +2+1. ]

Add term by term. Each pair sums to (n+1), and there are (n) pairs:

[ 2S=n(n+1). ]

Therefore:

[ S=rac{n(n+1)}2. ]

The proof exposes structure that the numerical list alone cannot.

43. Fresh conjecture 3

A learner checks several integers and believes (n^2+n+17) is always prime. The task is not to keep checking. Find a strategy for attacking the universal claim.

Try values related to the constant. At (n=17):

[ 17^2+17+17=17(17+2), ]

which is composite. The universal claim fails.

44. Fresh conjecture 4

Conjecture: if (amid b) and (amid c), then (amid(b+c)).

Proof: if (b=am) and (c=an) for integers (m,n), then:

[ b+c=a(m+n). ]

Since (m+n) is an integer, (amid(b+c)).

45. Fresh proof 1: odd plus odd

Prove the sum of two odd integers is even.

Let the odd integers be (2a+1) and (2b+1). Their sum is:

[ 2a+2b+2=2(a+b+1), ]

which is even.

46. Fresh proof 2: square parity

Prove: if (n) is odd, then (n^2) is odd.

Let (n=2k+1). Then:

[ n^2=4k^2+4k+1=2(2k^2+2k)+1. ]

47. Fresh proof 3: counterexample

Disprove: “For every real number (x), if (x^2>x), then (x>1).”

Take (x=-1). Then (x^2=1>-1=x), but (-1 ot>1). The statement is false.

48. Fresh proof 4: uniqueness

Prove that the equation (3x+4=10) has exactly one real solution.

Existence: (x=2) satisfies the equation.

Uniqueness: if (x_1) and (x_2) both satisfy it, then:

[ 3x_1+4=10=3x_2+4. ]

So (3x_1=3x_2), hence (x_1=x_2).

49. Fresh proof 5: set inclusion

To prove (Asubseteq B), begin with an arbitrary element (xin A) and show (xin B).

This is the set-theoretic form of universal reasoning: the chosen element is arbitrary, so the argument applies to all elements of (A).

50. Fresh proof 6: function injectivity

Let (f(x)=5x-7). Prove (f) is injective on (mathbb R).

Suppose:

[ f(a)=f(b). ]

Then:

[ 5a-7=5b-7, ]

so (a=b). Therefore (f) is injective.

51. A proof quality checklist

• Is the claim stated exactly?
• Is the domain explicit?
• Are the quantifiers clear?
• Did I use a definition where one is available?
• Does every line follow from the previous information?
• Did I prove the stated direction rather than the converse?
• Did I cover every case?
• Did I accidentally divide by zero or lose a branch?
• If I used examples, did I treat them as evidence rather than proof?
• If I used contradiction, what exactly was contradicted?
• If I used induction, where did the inductive hypothesis enter?
• Does the final line match the claim?

52. The transfer target

A learner is not proof-ready merely because they can reproduce a memorised induction template. Transfer appears when they can look at a new statement and decide:

• whether to search for a counterexample;
• whether a direct definition-based proof is natural;
• whether the contrapositive simplifies the structure;
• whether a case split is exhaustive;
• whether contradiction creates a useful constraint;
• whether induction matches a recursive or sequential claim;
• whether an extremal choice forces structure.

53. From successful cases to mathematical certainty

Numerical exploration is not the enemy of proof. It is often the beginning of proof.

Use examples to discover. Use counterexamples to attack. Use definitions to build. Use general reasoning to finish.

The durable loop is:

Explore → conjecture → state domain → test boundaries → choose proof structure → justify every inference → check the quantifier → conclude exactly what was claimed.

54. Continue through BTT Mathematics

Use School to University Mathematics Bridge for the wider transition into definitions, abstraction and independent study. Use How to Check Maths Answers for verification and first-invalid-step repair. Return to the World Mathematics Atlas for connected proof, olympiad and advanced Mathematics routes.

Proof Casebook: From Numerical Evidence to General Claims

This casebook extends the pattern-to-proof bridge with original problems. The recurring discipline is simple: examples can suggest a statement, but the proof must match the logical size of the claim.

Case 1: evenness from consecutive integers

Conjecture: the product of two consecutive integers is always even.

Write the integers as n and n+1. One of two consecutive integers must be even, so the product n(n+1) is even.

The proof is shorter than checking examples because the structure covers every integer at once.

Case 2: a conjecture that needs a domain

Conjecture: x²≥x.

This is true for integers but false for all real numbers. The counterexample x=1/2 gives 1/4<1/2.

Corrected claim: for every integer n, n²≥n.

The missing domain is not a technicality. It decides the truth value.

Case 3: a false converse

Statement: if an integer is divisible by 12, then it is divisible by 4.

Converse: if an integer is divisible by 4, then it is divisible by 12.

Counterexample: 8 is divisible by 4 but not by 12.

Olympiad proof writing often turns on noticing that an implication does not automatically reverse.

Case 4: strengthen the conjecture

A learner checks:

• 2²−2=2
• 4²−4=12
• 6²−6=30

and conjectures that n²−n is even for every even integer n.

Factor:

n²−n=n(n−1).

This is a product of consecutive integers, so it is even for every integer n. Proof reveals a stronger theorem than the original pattern suggested.

Case 5: find the first invalid inference

Proposed proof:

“Since x²≥0, therefore x≥0.”

The premise is true for all real x. The conclusion does not follow. Take x=-2. Then x²=4≥0 but x<0.

A proof can contain only true statements and still be invalid if the logical connection is wrong.

Case 6: direct proof from the definition of odd

Claim: the sum of two odd integers is even.

Let the odd integers be 2a+1 and 2b+1. Their sum is:

2a+1+2b+1=2(a+b+1).

Because a+b+1 is an integer, the sum is even.

The definition supplies the algebraic form that makes the proof possible.

Case 7: direct proof from divisibility

Claim: if m divides a and m divides b, then m divides a+b.

Write a=mk and b=mℓ for integers k,ℓ. Then:

a+b=m(k+ℓ).

Since k+ℓ is an integer, m divides a+b.

Case 8: proof by contrapositive

Claim: if n² is odd, then n is odd.

Contrapositive: if n is even, then n² is even.

Let n=2k. Then n²=4k²=2(2k²), which is even. Therefore the original statement holds.

The contrapositive is often cleaner because it aligns with the available definition.

Case 9: contradiction through parity

Claim: there is no integer n such that n is both even and odd.

Assume for contradiction that such an integer exists. Then n=2a and n=2b+1 for integers a,b. Hence:

2a=2b+1, so 2(a-b)=1.

The left side is even and the right side is odd, impossible. Therefore no such integer exists.

Case 10: the universal-existential distinction

Statement A: for every real x, there exists a real y such that y>x.

Statement B: there exists a real y such that for every real x, y>x.

A is true: choose y=x+1. B is false because the real numbers have no greatest element.

The same words appear. The quantifier order changes everything.

Case 11: negating a universal statement

Claim: “For every integer n, P(n) holds.”

Its negation is not “For every integer n, P(n) fails.”

The correct negation is:

“There exists an integer n such that P(n) fails.”

This is why one valid counterexample is enough to destroy a universal claim.

Case 12: negating an existential statement

Claim: “There exists a real number x with property P(x).”

The negation is:

“For every real number x, P(x) does not hold.”

Correct negation is essential in contradiction proofs.

Case 13: mathematical induction—sum of first n odd integers

Claim:

1+3+5+…+(2n−1)=n² for every positive integer n.

Base case. For n=1, both sides equal 1.

Inductive hypothesis. Assume the formula holds for n=k.

Inductive step. Then:

1+3+…+(2k−1)+(2k+1)=k²+2k+1=(k+1)².

Therefore the identity holds for all positive integers.

Case 14: induction fails if the bridge is missing

A learner writes: “The result works for n=1. Assume it works for n=k. The formula is obviously true for n=k+1.”

This is not induction because the proof never uses the inductive hypothesis to reach the next case.

The bridge from k to k+1 is the heart of the method.

Case 15: inequality by factoring

Claim: for every real x, x²−2x+1≥0.

Factor:

x²−2x+1=(x−1)².

A real square is non-negative, so the claim follows.

Proof quality often improves when the expression is rewritten into a form whose sign is structurally obvious.

Case 16: a universal claim killed by a boundary case

Claim: “If ab=ac, then b=c.”

Set a=0, b=1, c=2. Then ab=ac=0 but b≠c.

The corrected statement requires a≠0.

The boundary case reveals the missing condition.

Case 17: proof of uniqueness needs a second step

Suppose a problem asks for the unique solution of an equation or the unique object with a property.

Showing one object works proves existence, not uniqueness.

A uniqueness proof typically assumes two objects satisfy the condition and then shows they must be equal.

The word “unique” therefore creates an additional proof obligation.

Case 18: construct versus prove existence indirectly

To prove that there exists an even prime, simply construct one: 2.

Some existence proofs are less constructive. They show that at least one object must exist without identifying it explicitly. Olympiad students should learn to distinguish these proof styles rather than assume every existence statement demands a formula.

Case 19: a graph is not a proof of positivity

A graphing tool suggests that x⁴+1>0 for every real x.

The proof is immediate: x⁴≥0, so x⁴+1≥1>0.

The graph is useful evidence. The inequality argument has universal scope.

Case 20: a calculator search is not a proof of no solutions

A learner scans many numerical values and finds no integer solution to an equation. That may motivate a conjecture. It does not prove non-existence unless the search covers the entire finite domain or a theorem bounds the possibilities.

Proof must match the size of the search space.

Case 21: divisibility through modular structure

Claim: the square of any integer is congruent to 0 or 1 modulo 4.

Every integer is either even or odd.

If n=2k, then n²=4k²≡0 mod 4.

If n=2k+1, then n²=4k²+4k+1≡1 mod 4.

This short case split gives a reusable structural result.

Case 22: use the modular result to rule out an equation

Can x²+y²=4k+3 hold for integers x,y,k?

Squares are 0 or 1 modulo 4, so a sum of two squares can be congruent to 0, 1 or 2 modulo 4, but never 3. Therefore no such integers exist.

A prior lemma becomes a proof tool.

Case 23: proof by cases

Claim: for every integer n, n(n+1) is even.

Case 1: n is even, so the product is even.

Case 2: n is odd, so n+1 is even, and the product is even.

The cases exhaust all integers, so the proof is complete.

Case 24: cases must be exhaustive

If a proof considers positive and negative integers but forgets zero, it may be incomplete. The missing boundary case can matter.

Case analysis is valid only when the cases cover the stated domain.

Case 25: extremal principle—choose the largest or smallest object

In many olympiad arguments, the decisive move is to choose an extremal object: the largest number, smallest distance, earliest time, highest degree or shortest path.

Extremality turns a global configuration into a local constraint. The chosen object cannot be improved in the direction that defined it.

Case 26: extremal example with integers

Suppose a finite non-empty set of positive integers is closed under taking positive differences between distinct elements. Choose its smallest element m. For any other element a>m, the difference a−m is a positive element of the set. By minimality, a−m≥m, so a≥2m.

The smallest element imposes structure on every larger member.

Case 27: invariant thinking

An invariant is a quantity or property that remains unchanged under the allowed operations.

In a game where each move flips the colour of exactly two coins, the parity of the number of black coins may remain unchanged. If the target configuration has the wrong parity, the target is impossible.

Finding an invariant can replace a long search with a short impossibility proof.

Case 28: monovariant thinking

A monovariant moves only in one direction. It may increase or decrease at every step.

If a process strictly decreases a non-negative integer at each move, the process must eventually stop. This creates a termination proof without listing every state.

Case 29: pigeonhole principle

If 13 people are assigned to 12 birth months, at least two share a birth month.

The principle generalises: if more objects than boxes are distributed among the boxes, some box contains at least two objects.

The proof burden is not computational. It is recognising the hidden boxes and objects.

Case 30: strengthened pigeonhole

If 25 objects are placed into 6 boxes, some box contains at least:

ceil(25/6)=5

objects.

This quantitative version appears often in olympiad counting arguments.

Case 31: parity invariant in a board problem

Colour a chessboard in the usual black-and-white pattern. Any domino covering two adjacent squares covers one black and one white square.

If two opposite-colour counts are unequal after squares are removed, the remaining board cannot be tiled completely by dominoes.

The colouring creates an invariant that turns geometry into counting.

Case 32: counterexample should attack the exact claim

If the claim concerns positive integers, a negative number is irrelevant. If the claim concerns triangles, a quadrilateral is irrelevant.

A counterexample is decisive only when it belongs to the stated domain and violates the stated conclusion.

Case 33: avoid proving a stronger statement accidentally unless it is justified

Sometimes a proof establishes more than the problem asks. That is fine if the stronger statement is correct and fully proved.

But learners sometimes introduce a stronger claim that is false or harder than necessary. Proof design includes choosing the right logical target.

Case 34: sufficient versus necessary conditions

“Being divisible by 6” is sufficient for being divisible by 3. It is not necessary because 9 is divisible by 3 but not by 6.

Olympiad problems frequently become clearer when conditions are labelled as necessary, sufficient, both or neither.

Case 35: biconditional requires two directions

To prove P if and only if Q, prove:

1. P⇒Q;
2. Q⇒P.

One implication is only half the theorem.

Case 36: example of a biconditional

Claim: an integer n is even if and only if n² is even.

One direction follows immediately from n=2k. The reverse direction can be proved by contrapositive: if n is odd, then n² is odd.

Case 37: a proof should preserve variable roles

Do not silently change the meaning of a variable mid-proof. If n begins as an arbitrary integer, it cannot later become a specific tested value without explanation.

Variable discipline is part of proof clarity.

Case 38: arbitrary means fixed but unspecified

When a proof says “let n be an arbitrary integer”, n is fixed for the argument but not chosen to have any special property beyond being an integer.

This allows the conclusion to apply to every integer once the argument finishes.

Case 39: do not assume what you are trying to prove

Suppose the goal is to show two angles are equal. Beginning with “let the two angles be equal” destroys the proof because the conclusion has been inserted as an assumption.

Proof debugging should always ask: did the argument smuggle in the target?

Case 40: circular definitions and circular proofs

A proof is circular if it uses a result that itself depends on the theorem being proved. Circular reasoning can be difficult to notice when several equivalent formulas are familiar.

Keep the dependency chain explicit.

Case 41: algebra can prove a combinatorial identity

Some identities have more than one proof style. An algebraic expansion can prove a binomial identity; a counting argument can prove the same result by interpreting both sides as two ways to count the same set.

Comparing proof styles develops mathematical flexibility.

Case 42: double counting

Suppose a room contains n people and every pair shakes hands once. Count handshakes directly as pairs:

C(n,2)=n(n−1)/2.

Alternatively, count the total “handshake participation”: each person shakes n−1 hands, giving n(n−1) participations, and divide by 2 because each handshake was counted twice.

Two counts of the same quantity establish the identity.

Case 43: proof through a bijection

A bijection pairs objects in one set with objects in another without omission or duplication. If such a pairing exists, the sets have the same size.

Olympiad combinatorics often becomes easier when counting is replaced by constructing a correspondence.

Case 44: an inequality proof by AM-GM

For positive a,b:

(a+b)/2 ≥ sqrt(ab).

When a problem asks for a minimum or maximum, recognising the equality condition can be as important as applying the inequality.

The proof should state when equality occurs, not only the bound.

Case 45: equality cases belong to the theorem

If an inequality is sharp, identify the condition under which equality occurs. This often reveals the extremal configuration the problem is really asking about.

Case 46: constructive proof versus contradiction in geometry

A geometry result may be proved by constructing an auxiliary point or by assuming the desired configuration does not exist and deriving an impossibility. Proof method should follow structure, not habit.

Case 47: counterexample search strategy

When a universal claim feels suspicious, test boundary and extreme cases first:

• zero;
• one;
• negative values;
• equal variables;
• very small or very large cases;
• degenerate geometry;
• empty or singleton sets where permitted.

Good counterexamples are rarely random.

Case 48: proof search is not proof writing

Scratch work can contain diagrams, failed routes, numerical tests and informal notes. Final proof writing should present the valid dependency chain in a readable order.

Discovery order and proof order are often different.

Case 49: state the theorem before proving it

Especially in longer work, write the exact claim and domain first. This prevents the argument from drifting toward a nearby statement.

Case 50: the proof release checklist

• Is the claim stated precisely?
• Is the domain explicit?
• Are quantifiers correct?
• Are definitions used accurately?
• Does each step follow from a stated reason?
• Have all cases been covered?
• Has the conclusion actually been reached?
• Were existence and uniqueness separated if necessary?
• Were counterexamples tested against the correct domain?
• Is technology being used as evidence rather than proof where appropriate?

Fresh proof challenge 1

Prove that the sum of five consecutive integers is divisible by 5.

Let the integers be n,n+1,n+2,n+3,n+4. Their sum is:

5n+10=5(n+2),

which is divisible by 5.

Fresh proof challenge 2

Disprove: “For every real x, x²>x.”

Counterexample: x=0 gives equality, not strict inequality. Also x=1/2 gives x²<x.

Fresh proof challenge 3

Prove that if n is odd, then n²≡1 mod 8.

Write n=2k+1. Then:

n²=4k(k+1)+1.

One of k,k+1 is even, so k(k+1) is even and 4k(k+1) is divisible by 8. Hence n²≡1 mod 8.

Fresh proof challenge 4

Show that there is no greatest integer.

Suppose N were the greatest integer. Then N+1 is an integer and N+1>N, contradiction.

Fresh proof challenge 5

Prove that the square root of 2 is irrational.

Assume sqrt(2)=a/b in lowest terms. Then a²=2b², so a² is even, hence a is even. Write a=2k. Then 4k²=2b², so b²=2k², hence b is even. Both a and b are even, contradicting lowest terms.

The contradiction is created by a structural parity argument, not by decimal approximation.

Fresh proof challenge 6

Prove that if a and b are rational, then a+b is rational.

Write a=m/n and b=p/q with non-zero integers n,q. Then:

a+b=(mq+pn)/(nq),

a ratio of integers with non-zero denominator.

Fresh proof challenge 7

Find a counterexample to: “If a²=b², then a=b.”

Take a=1, b=-1. Then a²=b²=1 but a≠b.

The corrected conclusion over the reals is a=±b.

Fresh proof challenge 8

Prove that the sum of the first n positive integers is n(n+1)/2 by induction.

Base case n=1 is immediate. Assume:

1+2+…+k=k(k+1)/2.

Then:

1+2+…+k+(k+1)=k(k+1)/2+(k+1)

=(k+1)(k+2)/2.

Hence the formula holds for k+1.

Fresh proof challenge 9

Prove that among any 11 integers, two have the same remainder when divided by 10.

There are only 10 possible remainders: 0 through 9. By the pigeonhole principle, 11 integers placed into 10 remainder classes force at least one class to contain two integers.

Fresh proof challenge 10

Suppose a finite graph has every vertex of odd degree. Prove that the number of vertices is even.

The sum of all vertex degrees equals twice the number of edges, hence is even. A sum of an odd number of odd integers would be odd. Therefore the number of odd-degree vertices must be even.

This is the handshake lemma used as a parity proof.

How to practise proof efficiently

Do not read a solution and immediately conclude that the proof is understood. Close it and reconstruct the argument. Then change one condition.

• Change the domain.
• Reverse the implication.
• Ask whether the converse holds.
• Search for a counterexample.
• Try a different proof method.
• Identify the minimum assumption set.
• Explain where equality occurs.

Proof skill grows through reconstruction and variation, not recognition alone.

Proof and olympiad training

Olympiad problems often hide the proof method. The learner must first discover the structure and then present a rigorous argument. This means training needs both exploratory freedom and proof discipline.

A strong solution is not only ingenious. It is verifiable.

Proof and university preparation

Students moving toward university Mathematics should become comfortable with definitions, quantifiers, arbitrary objects, proof by contradiction, contrapositive reasoning and the distinction between examples and universal arguments.

Use the School to University Mathematics Bridge for the wider transition.

The proof compact

Discover with examples. State the claim precisely. Name the domain. Match the proof method to the logical structure. Test boundaries. Use counterexamples aggressively. Write the final argument in dependency order.

Proof Workshop: Discovery, Debugging and Release

Proof ability develops when students practise three different jobs deliberately: discovering a route, debugging an argument and writing a finished proof. These jobs overlap, but they should not be confused. A learner can discover the right idea and still write an incomplete proof. Another learner can copy elegant proof prose without understanding how the argument was found.

Workshop 1: separate scratch work from proof order

Scratch work is allowed to be messy. Try small cases, draw diagrams, expand expressions, guess invariants and test counterexamples. The finished proof should not reproduce every failed route. It should present the dependency chain that survived checking.

This separation helps students stop believing that expert proofs appear fully formed. Discovery can be exploratory; verification must be disciplined.

Workshop 2: identify the logical target

Before doing algebra, classify the statement:

• universal claim;
• existence claim;
• uniqueness claim;
• implication;
• biconditional;
• inequality;
• divisibility statement;
• extremal statement.

The logical form suggests what kind of evidence can possibly be sufficient.

Workshop 3: universal claims require arbitrary objects

To prove a statement for every integer, begin with an arbitrary integer—not a favourite example. The proof must use only properties guaranteed for every object in the domain.

If the argument quietly uses a special feature of the chosen example, the proof has not achieved universal scope.

Workshop 4: existence claims can be easier

To prove “there exists”, one valid construction may be enough. Students sometimes over-prove existence problems because they are accustomed to universal statements.

Example: prove there exists a positive integer whose square is greater than 100. The single construction 11 works because 11²=121>100.

Workshop 5: uniqueness adds a second burden

Suppose an equation has a solution x=a. Showing that a works proves existence. To prove uniqueness, show that any two solutions must be equal or show that no second solution can exist.

Students should underline the word “unique” because it changes the proof job.

Workshop 6: implication direction

If the theorem says P⇒Q, a proof of Q⇒P does not establish the theorem unless a biconditional is intended.

Write the direction explicitly at the top of the page when converse confusion is likely.

Workshop 7: prove a biconditional in two halves

Claim: an integer n is even if and only if n² is even.

Forward direction: if n=2k, then n²=4k² is even.

Reverse direction: prove the contrapositive. If n is odd, then n² is odd. Therefore if n² is even, n is even.

Both directions are necessary.

Workshop 8: choose direct proof when the definition opens the route

Direct proof is often best when the hypothesis can be translated immediately into a useful algebraic form.

Examples:

• even → 2k;
• odd → 2k+1;
• divisible by m → mk;
• rational → ratio of integers;
• subset → arbitrary element argument.

Workshop 9: choose contrapositive when the conclusion has a cleaner negation

For “if P, then Q”, the contrapositive is “if not Q, then not P”. It is logically equivalent.

Claims involving parity, divisibility and inequalities often become cleaner this way.

Workshop 10: choose contradiction when the opposite assumption creates structure

Contradiction is useful when assuming the negation forces an impossible parity, ordering, size or divisibility condition.

The proof should make the contradiction explicit. Do not end with vague language such as “which is impossible” without naming what has been violated.

Workshop 11: induction is a machine for linked integer cases

Induction works when the truth of one case can help build the next. It is not the default proof method for every statement involving n.

Before using induction, ask whether there is a natural recursive bridge from k to k+1.

Workshop 12: induction base cases can be plural

Some recurrences depend on the previous two cases. Then more than one base case may be required.

A proof that checks too few initial cases can leave the induction chain unstarted.

Workshop 13: strong induction

Strong induction allows the inductive step to assume the statement holds for all cases up to k, not only the single case k.

This is valuable when the next case depends on several smaller cases, as in factorisation or recurrence arguments.

Workshop 14: proof by cases needs an exhaustive partition

Common partitions include:

• even / odd;
• positive / zero / negative;
• inside / outside an interval;
• equal / unequal;
• several residue classes modulo m.

The cases must cover every object in the domain and should not leave hidden gaps.

Workshop 15: modular arithmetic compresses divisibility proofs

Instead of expanding large powers directly, work with remainders. If a≡b mod m, then addition and multiplication preserve congruence.

This makes periodicity and impossibility arguments much shorter.

Workshop 16: invariant proof search

When a process repeatedly transforms a configuration, ask what never changes:

• parity;
• sum modulo a number;
• colour count difference;
• orientation;
• product sign;
• gcd.

If the target has a different invariant value from the start, the target is unreachable.

Workshop 17: monovariant proof search

Sometimes nothing remains constant, but one measure moves in only one direction. A strictly decreasing non-negative integer cannot decrease forever.

Monovariants are powerful for proving termination.

Workshop 18: extremal choice

Choose the largest, smallest, earliest, latest, shortest or longest object. The extremal property often creates a contradiction if a forbidden configuration exists.

Extremal principle problems reward students who stop trying to control the whole system at once.

Workshop 19: pigeonhole design

The challenge is usually not applying the principle but choosing the boxes.

Ask:

• What classifications are limited in number?
• What objects are being placed?
• What collision would solve the problem?

Workshop 20: double counting

Count the same set of incidences in two different ways. Equality of the counts can produce identities or structural constraints.

The handshake lemma is the classic example: the sum of degrees equals twice the number of edges.

Workshop 21: construct a counterexample systematically

Test:

• zero;
• one;
• negative values;
• equal variables;
• extreme values;
• boundary cases;
• degenerate geometric cases.

A counterexample search should be strategic rather than random.

Workshop 22: repair an over-broad theorem

False statement: “If ab=ac, then b=c.”

Counterexample identifies the missing condition a≠0.

The learner should not stop at disproving the claim. Ask for the strongest natural corrected statement.

Workshop 23: remove unnecessary assumptions

A proof may begin with “let n be a positive even integer” even though the argument works for every integer. Unnecessary assumptions weaken the theorem and often reveal that the learner has not identified the real mechanism.

Workshop 24: equality conditions in inequalities

When proving an inequality, state when equality holds. The equality case often identifies the extremal configuration.

This is essential in optimisation-style olympiad problems.

Workshop 25: proof from a known theorem still needs condition checking

Quoting a theorem is not enough. The proof must establish that its hypotheses hold.

For example, applying a triangle theorem requires the correct geometric conditions; using a divisibility lemma requires the right domain.

Workshop 26: diagrams are discovery tools

A geometry diagram can inspire construction and pattern recognition. The final proof should use given or established properties, not visual appearance.

Mark which facts are given, which are constructed and which are proved.

Workshop 27: algebraic identities need domain awareness

Manipulations involving division, square roots or logarithms can change validity conditions. A formal algebraic sequence can be invalid at excluded values.

Proof writers should record domain restrictions before cancelling or applying inverse operations.

Workshop 28: proof by bounding

Exact evaluation may be unnecessary. If the goal is to show a quantity exceeds 100, a convenient lower bound above 100 is enough.

Bounding is a major olympiad habit because it replaces hard exact calculation with a strategically sufficient estimate.

Workshop 29: proof by symmetry

If a problem is symmetric in variables, exploit that structure. Symmetry can suggest equal cases, substitutions or a reduced parameter range.

But do not assume variables are equal merely because the statement is symmetric unless an extremal or equality argument justifies it.

Workshop 30: normalise when scale does not matter

In homogeneous problems, divide by a common scale or set one total to 1. Normalisation can reduce variables while preserving the essential relationship.

The learner should state why the transformation does not change the problem’s logical content.

Proof debugging drill 1: undefined division

Proposed proof divides both sides by x−2 before checking whether x=2. The division may discard a valid case.

Repair: separate the zero-factor case before dividing.

Proof debugging drill 2: squaring introduced candidates

Squaring both sides preserves every original solution but can introduce extra ones. A final substitution check is required.

This is a proof-level version of the reversible-step problem.

Proof debugging drill 3: taking square roots too narrowly

From x²=9, concluding x=3 loses x=-3.

The correct conclusion over the reals is x=±3.

Proof debugging drill 4: empirical generalisation

“The statement works for the first 100 integers, therefore it is true for all integers.” This is not a proof unless the domain itself has only those 100 cases.

Proof debugging drill 5: circular argument

If the proof uses a lemma whose proof depends on the theorem being established, the argument is circular even if every local step appears familiar.

Proof debugging drill 6: hidden converse

From “if a figure is a square, it is a rectangle”, a learner concludes “if a figure is a rectangle, it is a square.” The direction has been reversed.

Proof debugging drill 7: invalid quantifier swap

From “for every student there is a favourite book” one cannot infer “there is one book that is every student’s favourite”.

Quantifier order is not a typographical detail.

Proof debugging drill 8: case gap

A proof treats x>0 and x<0 but forgets x=0. If zero is in the domain, the proof is incomplete.

Proof debugging drill 9: unjustified equality condition

An inequality proof reaches a valid bound but claims equality at a point that does not satisfy every equality condition used along the route.

Track equality through each inequality step.

Proof debugging drill 10: conclusion too strong

The proof establishes that at least one solution exists but concludes that exactly one solution exists. Existence does not imply uniqueness.

Proof-writing style: name the objects

Avoid strings of symbols with no declared role. State “let n be an arbitrary integer” or “let x be an element of A”. This makes the scope of the argument visible.

Proof-writing style: explain decisive transitions

Routine algebra need not be narrated excessively, but the logical branch should be clear. Write why a contradiction occurs, why a theorem applies, or why a quantity is invariant.

Proof-writing style: do not hide behind “obvious”

If a step is genuinely immediate from a definition or established fact, keep it concise. If the step carries the argument, explain it. “Clearly” is not a substitute for a missing reason.

Proof-writing style: finish the claim you started

At the end, reconnect the conclusion to the theorem. If the goal was divisibility, state divisibility. If the goal was injectivity, state injectivity. Do not leave the reader to infer that the last algebraic line is enough.

Proof release test 1: reconstruction

After studying a proof, close the solution and reconstruct the argument from the theorem statement alone.

If only the wording is remembered, understanding is fragile. If the learner can regenerate the key idea and dependency chain, the proof is becoming owned.

Proof release test 2: changed numbers

Change constants while preserving the structure. Can the same proof method be adapted?

This distinguishes structural understanding from memorisation of one worked proof.

Proof release test 3: changed domain

Move from positive integers to all integers, or from integers to reals. Ask whether the claim survives.

Domain changes expose hidden assumptions quickly.

Proof release test 4: reverse the implication

Ask whether the converse is true. If false, find a counterexample. If true, prove it separately.

Proof release test 5: remove an assumption

Delete one hypothesis and search for a counterexample. If none appears, attempt a proof of the stronger theorem.

This exercise teaches which assumptions are load-bearing.

Proof release test 6: choose a different method

A theorem proved by induction may have a direct algebraic or combinatorial proof. Comparing routes develops method awareness.

Proof release test 7: debug a planted error

Give the learner a proof containing one plausible invalid inference. Ask for the first bad line and the smallest repair.

This develops proof checking, not only proof production.

Proof release test 8: explain the role of each line

Can the learner say which line activates a definition, uses an assumption, invokes a theorem or closes the proof?

A proof becomes easier to remember when its architecture is understood.

Proof release test 9: write for another reader

The final proof should be readable by someone who knows the prerequisite Mathematics but has not seen the scratch work.

That is the standard of verifiability.

Proof release test 10: delayed return

Revisit the theorem after several days. Can the learner reconstruct the central idea without the original solution?

Durable proof knowledge should survive more than immediate recognition.

Parent guide: what proof progress looks like

Proof improvement may appear before olympiad results move:

• claims become more precise;
• domains are stated more often;
• counterexamples are searched earlier;
• converse errors reduce;
• definitions are activated without prompting;
• proofs become shorter because the decisive structure is found sooner;
• the student can explain where a proof attempt fails.

Tutor guide: when to give a hint

If a learner has not yet identified the logical form of the claim, a hint can point there without giving the proof. Ask:

• Is the claim universal or existential?
• What does the key definition give you?
• Would the contrapositive be easier?
• Can you find a counterexample?
• What quantity stays invariant?
• What is the smallest or largest object?

The best hint changes the search space while leaving the proof act to the student.

Final proof standard

A strong proof is not impressive because it is long. It is strong because the claim is precise, the assumptions are visible, every decisive inference is valid and the conclusion matches the logical scope of the theorem.

Explore freely. Prove narrowly. Write so another mathematician can verify the route.

Final Proof Training Lab: Ten Ways to Make an Argument More Reliable

1. State the claim before the algebra begins

A proof is easier to control when the learner knows exactly what must be established. Rewrite the theorem in one sentence, including its domain and quantifiers. This prevents a long argument from drifting toward a nearby but different statement.

2. Mark the hypotheses

Underline every assumption. If the problem says positive integers, right triangle, non-zero real number, continuous function or finite set, ask where each condition enters the argument.

If a hypothesis is never used, either the theorem may be stronger than stated or the proof may be missing something.

3. Mark the conclusion

Proofs often end one step early. A learner may derive an equation and forget to reconnect it to divisibility, parity, injectivity or the required inequality. The final sentence should state why the last line closes the original claim.

4. Identify the decisive line

Most proofs contain one structural move that matters more than the routine manipulation around it: factoring consecutive integers, choosing an extremal object, introducing a useful auxiliary line, switching to the contrapositive or finding the invariant.

Ask the learner to circle that line. If they cannot identify it, they may remember the sequence without understanding the proof idea.

5. Test the proof on a boundary case

Before releasing the argument, inspect zero, equality cases, smallest allowed values or degenerate configurations. Boundary cases frequently expose hidden division by zero, missing sign conditions or incomplete case splits.

6. Ask what would break if one assumption were removed

Delete one hypothesis and search for a counterexample. This converts assumptions from passive text into active structural components.

Example: remove a≠0 from cancellation ab=ac⇒b=c. The case a=0 immediately shows why the condition is load-bearing.

7. Ask whether the converse is true

After proving P⇒Q, test Q⇒P. If the converse fails, find a clean counterexample. If it holds, prove it separately and upgrade the result to a biconditional.

This exercise strengthens implication discipline and often reveals a deeper theorem.

8. Compare with a second proof method

Where possible, prove the same result another way. An algebraic identity may also have a combinatorial proof. An inequality may have a geometric interpretation. A divisibility result may be proved directly or with modular arithmetic.

Different proofs expose different structure. The goal is not duplication but perspective.

9. Reconstruct after delay

A proof that feels obvious while open on the page can disappear quickly. Return after several days and ask for the theorem statement, proof idea and decisive inference without notes.

Delayed reconstruction is stronger evidence than immediate recognition.

10. Write for a sceptical reader

Imagine the reader accepts standard definitions and established theorems but nothing else. Every decisive claim should have a reason they can inspect.

This does not require excessive prose. It requires enough structure that the argument can be verified independently.

Mini proof audit A

Claim: the product of three consecutive integers is divisible by 6.

Let the integers be n,n+1,n+2. Among three consecutive integers, one is divisible by 3. At least one is even. Therefore their product contains factors 2 and 3 and is divisible by 6.

Audit:

• Domain: integers.
• Decisive structure: residue coverage across three consecutive integers.
• No case is omitted.
• The conclusion matches the divisibility claim.

Mini proof audit B

Claim: for real x, x+1/x≥2.

This statement needs the condition x>0. If x=-1, the left side is −2.

Corrected claim: for x>0, AM-GM gives:

(x+1/x)/2 ≥ sqrt(x·1/x)=1,

so x+1/x≥2, with equality at x=1.

The counterexample did not merely reject the original claim; it helped repair its domain.

Mini proof audit C

Claim: there are infinitely many even integers.

Suppose there were only finitely many, with a largest even integer N. Then N+2 is also even and larger than N, contradiction.

The proof uses an extremal assumption—the supposed largest object—to create the contradiction.

Mini proof audit D

Claim: if a,b are odd integers, then ab is odd.

Write a=2m+1 and b=2n+1. Then:

ab=4mn+2m+2n+1=2(2mn+m+n)+1.

The result has the defining form of an odd integer.

The proof starts and ends with the definition.

What proof maturity looks like

The mature learner increasingly does the following without prompts:

• states the domain;
• reads quantifiers carefully;
• tests the converse;
• searches for boundary counterexamples;
• activates definitions;
• chooses a proof method from the logical structure;
• checks whether assumptions were used;
• separates exploration from final proof order;
• reconstructs important arguments after delay.

Olympiad proof writing becomes powerful when the student can both discover and certify. Ingenuity finds the route; rigour shows that the route actually reaches the theorem.