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.
Start with the warm-up and record your first reasoning.
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?
Orient yourself to the lesson goals, language, and core approach.
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$
Work through the concept and complete its check.
The decision flow used by experienced provers:
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$.
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"?
Build the next proof move and complete its check.
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."
$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$.
Follow the worked examples, then complete the check.
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.
Fill the gap: The claim "for all real $x$, $x^2 \geq x$" is FALSE. The simplest counterexample is $x = \dfrac{p}{2}$ with $p =$ , where $x^2 = \tfrac{1}{4} < x = \tfrac{1}{2}$.
Correct the common traps and test your understanding.
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$.
Complete the practice activities and revisit your opening thinking.
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.
Multiple choice, then short answer under exam conditions.
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)
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].
Sit the module quiz, then close the lesson off.
A full module quiz covering every lesson in this module, not just this one. Set aside a decent block of time and treat it like a real assessment.
Start the module quiz →Tick when you've finished the practice and review.
Work through this topic 1-on-1 with an experienced HSC tutor.
Book a free session →