Proof (AA HL)
Proof is where AA HL asks you to argue with complete rigour rather than just compute an answer. This topic covers three techniques: proof by mathematical induction, which shows a statement holds for every positive integer by climbing a ladder of implications; proof by contradiction, which assumes the opposite of what you want and derives an impossibility; and disproof by a single, clearly explained counterexample.
What the syllabus says
This topic maps onto one point in the official IB Analysis & Approaches syllabus, covering three related proof techniques.
| Code | Syllabus content |
|---|---|
| AHL1.15 | Proof by mathematical induction. Induction links to a wide variety of topics, including complex numbers (De Moivre's theorem), differentiation, sums of sequences and divisibility. |
| AHL1.15 | Proof by contradiction, e.g. the irrationality of \(\sqrt3\) or the cube root of 5, or Euclid's proof that there are infinitely many primes. Use of a counterexample to show that a statement is not always true - it is not sufficient to state the counterexample alone; you must explain why it disproves the statement. |
Proof is examined throughout the AA HL course wherever it applies, not only as a standalone topic.
Key terms
Five words worth knowing cold before you touch a proof question - each with a worked example showing exactly what it means.
What is proof by mathematical induction?
Induction proves a statement is true for every integer from a starting value upward, by showing it holds at the start and that truth at one stage forces truth at the next. It's the standard technique for statements about "all positive integers \(n\)", especially sums, divisibility, and derivatives.
e.g. To prove \(1+3+5+\cdots+(2n-1)=n^2\), check \(n=1\): LHS \(=1\), RHS \(=1^2=1\). ✓
What is the base case?
The base case is the first value of \(n\) for which you verify the statement directly by substitution - usually \(n=1\), but sometimes higher if the statement only holds from some point on. Without it, the inductive step alone proves nothing, since there's no starting rung to climb from.
e.g. For \(2^n>n^2\) (true for \(n\ge5\)), the base case is \(n=5\): \(2^5=32>25=5^2\). ✓
What is the inductive step?
The inductive step assumes the statement is true for \(n=k\) (the hypothesis) and uses that assumption to prove it must then be true for \(n=k+1\). This is the algebraic heart of the proof - you're not proving the statement from scratch, only that truth is passed along.
e.g. Assuming \(1+3+\cdots+(2k-1)=k^2\), adding \((2k+1)\) gives \(k^2+2k+1=(k+1)^2\), matching \(n=k+1\).
What is proof by contradiction?
Proof by contradiction assumes the opposite of what you're trying to show, then reasons logically until you reach something impossible - which means the original assumption must have been false, so the statement you wanted is true.
e.g. Assume \(\sqrt2=\tfrac pq\) in lowest terms; this forces both \(p\) and \(q\) to be even, contradicting "lowest terms".
What is a counterexample?
A counterexample is a single case where a general claim fails - enough to disprove "always true" statements, since one failure is sufficient. You must state the case and explain why it fails, not just assert it.
e.g. \(n^2+n+41\) is prime for \(n=0,\ldots,39\), but at \(n=40\): \(40^2+40+41=1681=41^2\), which is not prime.
Key formulas
Proof doesn't use "formulas" in the usual sense - it uses fixed argument structures, plus a handful of series formulas that turn up as common induction targets. The tables below cover both.
Formula reference
The proof structures themselves aren't in the formula booklet - they're a method you apply, not a value you look up. The sum-of-roots style series formulas below are common induction targets and some are booklet formulas in their own right.
| Formula / structure | Used for | Booklet? |
|---|---|---|
| Base case → hypothesis → inductive step → conclusion | Induction proof structure | Not in booklet - method |
| Assume negation → derive contradiction → conclude | Contradiction proof structure | Not in booklet - method |
| State the failing case → explain why it fails | Disproof by counterexample | Not in booklet - method |
| \(\displaystyle\sum_{r=1}^n r = \dfrac{n(n+1)}{2}\) | Common induction target (sum of naturals) | Not in booklet - derivable from the arithmetic series formula |
| \(\displaystyle\sum_{r=1}^n r^3 = \dfrac{n^2(n+1)^2}{4}\) | Common induction target (sum of cubes) | Not in booklet |
| \((\cos\theta+i\sin\theta)^n=\cos n\theta+i\sin n\theta\) | De Moivre's theorem, often proved by induction | ✓ Yes |
Induction, contradiction and counterexample compared
All three techniques prove or disprove a statement, but they attack it from different directions - this table lines them up.
| Technique | What it proves | Core move |
|---|---|---|
| Induction | A statement holds for every integer \(n\ge n_0\) | Show truth at \(n=k\) forces truth at \(n=k+1\) |
| Contradiction | A statement is true (often "there is no...", or irrationality) | Assume the statement is false and derive an impossibility |
| Counterexample | A general claim is false | Produce one case where the claim fails, and explain why |
The structure of an induction proof
Every induction proof on this topic follows the same four-part skeleton, whatever the statement being proved.
Base case
Verify the statement directly for the smallest value of \(n\) (usually \(n=1\)) by substitution.
Inductive hypothesis
Assume the statement is true for \(n=k\) - write this assumption down explicitly.
Inductive step
Use the hypothesis to show the statement must then hold for \(n=k+1\).
Conclusion
State that the result is true for the base case, and that truth for \(n=k\) implies truth for \(n=k+1\), so by induction it holds for all \(n\) in the stated range.
The structure of a contradiction proof
Contradiction proofs follow a shorter three-part pattern.
Assume the negation
Start by assuming the opposite of what you want to prove, stated precisely (e.g. "assume \(\sqrt2\) is rational, so \(\sqrt2=\tfrac pq\) in lowest terms").
Derive a contradiction
Reason forward using valid algebra or logic until you reach something impossible - two things that can't both be true.
Conclude
State that the assumption must be false, so the original statement is true.
Worked examples
Two full exam-style questions, marked exactly like the real thing. Try each one yourself before checking the worked solution.
Prove by induction that \(\displaystyle\sum_{r=1}^{n} r = \frac{n(n+1)}{2}\) for all \(n\in\mathbb{Z}^+\).
Worked solution
\((n=1)\): LHS \(= 1\); RHS \(= \dfrac{1(2)}{2} = 1.\) Equal, so the statement holds for \(n=1.\) A1
Assume \(\sum_{r=1}^{k} r = \dfrac{k(k+1)}{2}.\) M1
Add the \((k+1)\)th term: \(\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1).\) M1
\(= (k+1)\left(\dfrac{k}{2} + 1\right)\) A1
\(= \dfrac{(k+1)(k+2)}{2}.\) A1
True for \(n=1\), and truth for \(n=k\) implies truth for \(n=k+1\); hence by induction it holds for all \(n\in\mathbb{Z}^+.\) R1
Prove by contradiction that \(\sqrt{2}\) is irrational.
Worked solution
Assume \(\sqrt2\) is rational, so \(\sqrt2 = \dfrac{p}{q}\) in lowest terms (\(\gcd(p,q)=1\)). M1
Then \(2 = \dfrac{p^2}{q^2} \Rightarrow p^2\) A1
\(= 2q^2\), so \(p^2\) is even, hence \(p\) is even. A1
Write \(p = 2a.\) M1
Then \(4a^2 = 2q^2 \Rightarrow q^2 = 2a^2\), so \(q\) is even. A1
But then \(2\) divides both \(p\) and \(q\), contradicting \(\gcd(p,q)=1.\) A1
Hence \(\sqrt2\) is irrational. R1 ∎
Common mistakes
The four slip-ups that account for most of the marks lost on this topic - worth reading before you start practising, not just after you get one wrong.
- Assuming what you're trying to prove. Writing "\(n=k+1\)" and then just asserting the target form is circular - you must derive it algebraically from the inductive hypothesis, step by step.
- Skipping or rushing the base case. Without an explicit, correct verification at the starting value, the whole induction has no foundation to climb from - it's worth a mark on its own.
- Not stating the contradiction explicitly. Reaching "\(p\) and \(q\) are both even" is only half the job - you must say what this contradicts (the assumption that \(\gcd(p,q)=1\)).
- Giving a counterexample without explaining it. The syllabus is explicit: it's not sufficient to state the counterexample alone. Show why the case breaks the general claim.
Using your GDC
Proof questions themselves are always non-calculator - every worked example above was solved with algebra alone. But two general GDC skills are worth having ready for calculator papers elsewhere in this unit: entering results in scientific notation, and solving equations numerically to explore a pattern before you try to prove it. Pick your model to filter down to just the steps that apply to you.
For very large or very small numbers - avoids typing long strings of zeros and prevents rounding errors, useful when checking a divisibility or growth statement for a large \(n\) before you prove it.
- Scientific notation means \(a \times 10^n\), e.g. \(3.2 \times 10^8\) or \(4.5 \times 10^{-3}.\)
- Use 2nd → , (EE) to enter the ×10 part: type 3.2 2nd , 8 to enter \(3.2\times10^8.\) Do NOT type ×10^ separately.TI-84
- Use the EE key (or type ×10^ from the keyboard template). Or just type 3.2×10^8 using the ^ key.Nspire
- Use the ×10ˣ key (EXP key) - type 3.2 then EXP then 8. Do NOT type ×10^ manually.Casio
- To display answers in scientific notation: on TI-84 press MODE and choose SCI; on Casio set the display mode in SET UP.
Tip: A common mistake is typing ×10^ instead of using the EE/EXP key - this gives ×10×... (multiplication, then a power) rather than proper scientific notation.
Faster and safer than algebra for messy equations - useful for testing whether a conjectured identity or inequality actually holds before you commit to writing a full induction or contradiction proof.
- Graph \(f(x)\) first so you can see how many solutions exist and roughly where they are.
- Rearrange so everything is on one side: \(f(x)=0\) - or graph both sides as separate functions and find intersections.
- MATH → Solver: enter the expression, type a starting guess close to one root, press ALPHA + ENTER. Move the guess to near a different root and repeat for each solution.TI-84
- Type nSolve(f(x)=0, x, guess) - include a guess or interval e.g. nSolve(f(x)=0, x, 2) or nSolve(f(x)=0, x, {1,5}) to target a specific root.Nspire
- Run-Matrix → SolveN(f(x), x) returns all real roots at once; or use the Equation app for a visual approach.Casio
- Always verify each solution by substituting back into the original equation.
Tip: The solver finds ONE root near your starting guess - change the guess to find others. The graph shows you how many to expect.
See the full GDC guide for more calculator models and topics.
Ready to practise properly?
Proof questions, marked instantly like the real exam.
Quick answers
The questions students on this topic ask most often.
What's the difference between induction and contradiction?
Induction proves a statement holds for every value in a sequence (usually every positive integer) by showing it's true for a starting value and that truth at one stage forces truth at the next. Contradiction proves a statement by assuming it's false and showing that assumption leads to something impossible.
Do I need to write "let P(n) be the statement..." in an induction proof?
It's good practice and helps structure your answer, but examiners mark the substance - a clearly labelled base case, hypothesis, inductive step, and conclusion referencing induction. Missing the conclusion sentence is the most common reason marks are lost.
Is a counterexample enough on its own to disprove a statement?
No. The syllabus is explicit that it is not sufficient to state a counterexample alone - you must explain why it fails the original statement, e.g. by showing the resulting number is not prime and giving its factors.
Can I use my GDC for proof questions?
Proof questions themselves are always non-calculator - induction and contradiction are algebraic arguments. But your GDC is useful beforehand, for testing a conjecture on several values to see whether it looks true before you commit to proving it. See the GDC guide for model-specific instructions.
Sub-topics
Proof broken down into its individual skills, each with its own focused page.
Related topics
More Number & Algebra topics from the same AA HL syllabus unit, in case you want to keep going.