Mixed Proof Techniques
Faced with the claim "for every integer $n$, if $n^2$ is even then $n$ is even" — which proof technique do you reach for first? Direct? Contradiction? Contrapositive? Real mathematicians don't memorise one method; they read the statement, judge the structure, and pick the cleanest route. This lesson trains that judgment, then drills three problems where two valid proofs both work — so you can compare and choose.
Consider the claim: for every integer $n$, if $n^2$ is even then $n$ is even. Before consulting any rule — which proof technique would you choose, and what would your first line of working be?
Every proof question rewards two habits: read the statement's logical form first (is it "if P then Q"? a universal claim? an existence claim?), then pick the method whose machinery matches that form. Jumping into algebra without classifying the statement is the single biggest cause of stuck proofs.
The read-and-match strategy: (1) classify the statement (implication, universal, existence, negation), (2) match to a method (direct, contrapositive, contradiction, induction, counterexample), (3) write the opening line precisely before doing any algebra.
Direct: assume $P$, derive $Q$ · Contrapositive: assume $\neg Q$, derive $\neg P$ · Contradiction: assume $P \wedge \neg Q$, derive $\bot$
Key facts
- Direct proof: assume $P$, deduce $Q$
- Contrapositive: $P \Rightarrow Q$ is logically equivalent to $\neg Q \Rightarrow \neg P$
- Contradiction: assume $P \wedge \neg Q$ and derive a false statement
- One counterexample disproves a universal claim
Concepts
- Why the structure of a statement points to a method
- Why two valid proofs of the same result can use different techniques
- When induction is overkill (or underkill) vs. direct or contradiction
Skills
- Read a proof prompt and pick a method within 30 seconds
- Write the correct opening line for direct, contrapositive, contradiction and induction proofs
- Recognise when a counterexample is required (a single failure disproves a universal)
The decision flow used by experienced provers:
- Is it a universal claim "for all $n$, $P(n)$"? If yes and $P(k)$ feeds $P(k+1)$ → induction. If you can find one failure → counterexample (statement is false).
- Is it "if $P$ then $Q$" with $P$ a clean handle? Try direct proof: assume $P$ and unfold definitions toward $Q$.
- Is $\neg Q$ much easier to work with than $Q$? Use the contrapositive: assume $\neg Q$, deduce $\neg P$.
- Is the claim a denial ("$x$ is irrational", "no largest prime", "no integer solution")? Use contradiction: assume the opposite and chase a false consequence.
The hook revisited: Prove $\sqrt{2}$ is irrational. The statement is a denial ("$\sqrt{2}$ is NOT a ratio of integers"). The decision tree points to contradiction: assume $\sqrt{2} = p/q$ with $\gcd(p,q)=1$, square both sides, deduce $p$ and $q$ are both even — contradicting $\gcd(p,q)=1$.
- Step 1: assume $\sqrt{2} = p/q$ in lowest terms, so $\gcd(p,q)=1$.
- Step 2: square: $2 = p^2/q^2$, so $p^2 = 2q^2$. Hence $p^2$ is even, so $p$ is even (using the contrapositive lemma!). Write $p = 2m$.
- Step 3: $4m^2 = 2q^2 \Rightarrow q^2 = 2m^2$, so $q^2$ is even, so $q$ is even. But $p$ and $q$ are both even contradicts $\gcd(p,q)=1$. $\blacksquare$
Decision flow: universal+inductive → induction · universal+one failure → counterexample · clean hypothesis → direct · cleaner negation → contrapositive · denial/no-such → contradiction · $\sqrt{2}$ irrational: contradiction shell, contrapositive lemma inside · Lemma: $n^2$ even $\Rightarrow$ $n$ even (proved by contrapositive: $n = 2k+1 \Rightarrow n^2 = 4k^2+4k+1$ odd)
Pause — copy the five-trigger decision flow (universal+inductive, universal+failure, clean hypothesis, clean negation, denial) and the $\sqrt{2}$ irrationality strategy (contradiction shell + contrapositive lemma) into your book.
Quick check: Which proof technique is best suited to the claim "for every integer $n$, if $n^3$ is odd then $n$ is odd"?
We just saw the decision tree: inductive structure → induction, one failure → counterexample, clean hypothesis → direct, cleaner negation → contrapositive, "no-such" statement → contradiction. That raises a question: what if two methods both give a clean proof? This card answers it → $n^2$ even $\Rightarrow n$ even admits both contrapositive and contradiction proofs; choosing the cleaner one is correct mathematical practice.
Many HSC proof prompts admit more than one valid method. Knowing the alternatives is what scores top-band marks — and lets you pivot when one route stalls.
Example: "Prove that if $n^2$ is even then $n$ is even."
- Contrapositive (cleanest): Assume $n$ is odd. Then $n = 2k+1$, so $n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1$, which is odd. Hence if $n^2$ is even, $n$ cannot be odd, so $n$ is even. $\blacksquare$
- Contradiction (also valid): Suppose $n^2$ is even but $n$ is odd. Then $n = 2k+1$ for some integer $k$, so $n^2 = 4k^2+4k+1$ is odd — contradicting that $n^2$ is even. So $n$ is even. $\blacksquare$
$n^2$ even $\Rightarrow$ $n$ even has two clean proofs: contrapositive and contradiction · Contrapositive proof ends by showing $\neg Q \Rightarrow \neg P$; contradiction ends with $\bot$ · $n = 2k+1 \Rightarrow n^2 = 2(2k^2+2k)+1$ (odd) · Two routes to the same conclusion is a feature, not a bug — pick the cleaner one
Pause — copy both proofs of "$n^2$ even $\Rightarrow n$ even": the contrapositive ($n = 2k+1 \Rightarrow n^2$ odd) and the contradiction form, and note that either is acceptable into your book.
Did you get this? True or false: a proof by contrapositive of "$P \Rightarrow Q$" begins by assuming $\neg Q$ and ends by deriving $\neg P$.
Worked examples · 3 in a row, reveal as you go
Prove that for every integer $n$, if $5n+3$ is even then $n$ is odd. Give (a) a direct proof and (b) a contrapositive proof. Comment on which is cleaner.
Prove that there are infinitely many prime numbers. Give a contradiction-style proof, then sketch a direct constructive proof.
Prove that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all positive integers $n$. Give (a) a proof by induction and (b) a direct proof using the Gauss pairing argument.
$S = 1 + 2 + \cdots + n$
$S = n + (n-1) + \cdots + 1$
Add term-by-term: $2S = (n+1) + (n+1) + \cdots + (n+1) = n(n+1)$. Hence $S = \dfrac{n(n+1)}{2}$. $\blacksquare$
Fill the gap: The claim "for all real $x$, $x^2 \geq x$" is FALSE. The simplest counterexample is $x = \dfrac{}{2}$, where $x^2 = \tfrac{1}{4} < x = \tfrac{1}{2}$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: to disprove the claim "for every prime $p$, $2^p - 1$ is prime", it is sufficient to show that $2^{11} - 1 = 2047 = 23 \times 89$.
Activities · practice with the ideas
Prove by contrapositive: for every integer $n$, if $n^2 + 1$ is even then $n$ is odd.
Prove by contradiction: there is no smallest positive rational number.
Give two valid proofs of the identity $1^3 + 2^3 + \cdots + n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$: one by induction and one by the direct argument $1^3+\cdots+n^3 = (1+2+\cdots+n)^2$.
Disprove with a single counterexample: "For all positive integers $n$, the expression $n^2 + n + 41$ is prime."
A student writes: "Suppose $\sqrt{2}$ is rational. Then $\sqrt{2} = a/b$ in lowest terms. Squaring gives $2b^2 = a^2$, so $a$ is even. We have shown $a$ is even — therefore $\sqrt{2}$ is irrational." Identify the structural flaw in this argument and write a correct one-paragraph completion.
Odd one out: Three of these openings are correctly matched to their method. Which one is NOT?
Earlier you considered which method to use to prove "$n^2$ even $\Rightarrow$ $n$ even".
Both contrapositive and contradiction are valid here. The contrapositive is cleaner because $\neg Q$ ("$n$ is odd") gives a direct algebraic handle $n = 2k+1$, and $n^2 = 4k^2+4k+1$ is immediately seen as odd. The contradiction version derives the same fact and then says "$n^2$ odd contradicts $n^2$ even", which is the same content packaged differently. Picking the cleaner shape is the skill this lesson trains.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove by contrapositive: for every integer $n$, if $3n+5$ is odd then $n$ is even. (2 marks)
Q2. Prove by contradiction that $\sqrt{3}$ is irrational. Make every step of the logical structure explicit (assumption, algebra, contradiction, conclusion). (3 marks)
Q3. Prove that $n^3 - n$ is divisible by $6$ for every positive integer $n$. Give (a) an induction proof and (b) a direct proof using the factorisation $n^3 - n = (n-1)n(n+1)$. Comment briefly on which is more insightful. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Contrapositive: assume $n$ is even, $n = 2k$. Then $n^2 + 1 = 4k^2 + 1$, which is odd. So if $n^2+1$ is even, $n$ cannot be even, i.e., $n$ is odd. $\blacksquare$
2. Suppose $q > 0$ is the smallest positive rational. Then $q/2$ is also a positive rational and $q/2 < q$, contradicting minimality. So no smallest positive rational exists. $\blacksquare$
3. Induction: base $n=1$: $1 = 1$. Step: $\sum_1^{k+1} m^3 = \left(\tfrac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\!\left(\tfrac{k^2}{4} + (k+1)\right) = \tfrac{(k+1)^2(k+2)^2}{4}$ ✓. Direct: use $\sum_1^n m = \tfrac{n(n+1)}{2}$, then square; verified by induction on the partial-sum identity.
4. $n = 40$: $40^2 + 40 + 41 = 1681 = 41^2$. Not prime. Counterexample. $\blacksquare$
5. Flaw: the argument stops after "$a$ is even" — no contradiction has been derived. Completion: write $a = 2m$, so $2b^2 = 4m^2$, giving $b^2 = 2m^2$. Hence $b$ is also even, contradicting $\gcd(a,b)=1$. Therefore $\sqrt{2}$ is irrational. $\blacksquare$
Q1 (2 marks): Assume $n$ is odd, $n=2k+1$ [1]. Then $3n+5 = 6k+8 = 2(3k+4)$ is even. So if $3n+5$ is odd, $n$ is not odd, i.e., $n$ is even [1]. $\blacksquare$
Q2 (3 marks): Suppose $\sqrt{3} = p/q$ in lowest terms [1]. Then $3q^2 = p^2$, so $3 \mid p^2$, hence $3 \mid p$. Write $p = 3m$, then $q^2 = 3m^2$, so $3 \mid q$ [1]. But $3 \mid p$ and $3 \mid q$ contradicts $\gcd(p,q) = 1$. Therefore $\sqrt{3}$ is irrational [1]. $\blacksquare$
Q3 (3 marks): (a) Induction: base $n=1$: $0$ divisible by 6 ✓. Step: $(k+1)^3-(k+1) = k^3+3k^2+3k+1-k-1 = (k^3-k)+3k(k+1)$. First term divisible by 6 (IH), second is $3 \times \text{even}$, so divisible by 6. Hence divisible by 6 [1]. (b) Direct: $n^3-n = (n-1)n(n+1)$, three consecutive integers, so the product is divisible by 2 (one is even) and by 3 (one is a multiple of 3), hence by 6 [1]. Comment: direct is more insightful because the factorisation immediately reveals the divisibility structure [1].
Five timed prompts. Read each statement, pick the cleanest method, and write the opening line. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by classifying proof statements and matching them to methods. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.