IB Practice / Maths AA HL / Number and algebra

Proof: direct, by contradiction, by counterexample and by induction: study notes

Proof is the part of the course where you must show, with a complete chain of reasoning, that a statement is true for every case it claims to cover, or show with a single counterexample that it is not. SL 1.6 covers direct deductive proof (a left-hand side to right-hand side argument, numerical or algebraic) together with the symbols and notation for equality and identity (== and ≡\equiv). The AHL content (1.15) adds proof by mathematical induction (a long-answer staple that usually appears on Paper 1, can appear on Paper 2 and sometimes closes a Paper 3 investigation), proof by contradiction, and disproof by counterexample. Nothing for this topic is in the formula booklet; marks are earned by layout, precise language and a full closing statement.

Download the PDFFree, no sign-up.

1. Direct deductive proof, numerical and algebraic

A direct proof starts from definitions and known results and moves by valid steps to the statement required. The essential skill is to represent a general object with algebra rather than a number: an even integer is 2m2m, an odd integer is 2m+12m+1, consecutive integers are nn and n+1n+1, a multiple of 3 is 3m3m, with m,n∈Zm, n \in \mathbb{Z}. Checking a few numerical cases is never a proof of a general statement and earns nothing. For a 'show that' with a printed target, lay out the argument from one side only: write LHS ==, manipulate line by line, and finish with the exact printed expression followed by == RHS. Do not treat the identity as an equation and perform operations on both sides at once, because that assumes what is to be proved. Choose the more complicated side to start from, since simplifying is easier to justify than expanding.

2. The symbols and the language of proof

Every line must follow from the previous one, and the words make that link visible. Use 'since', 'because' and 'as' to give reasons; 'hence', 'therefore', 'so' and the symbol ∴\therefore to draw conclusions; ⇒\Rightarrow for 'implies' and ⇔\Leftrightarrow only when the reverse direction is genuinely valid. Define every letter you introduce ('let n∈Z+n \in \mathbb{Z}^+') and state the domain the statement covers. Close with a sentence: 'as required', 'which is the result', QED, or the filled square ■\blacksquare. Examiners typically reserve an R mark for this reasoning and for the correct statement of what has been proved, so a proof that stops at the last line of algebra is not finished.

3. Proof of identities

Identities (often trigonometric or algebraic) are proved LHS to RHS using the identity sign ≡\equiv or a chain of equals signs. Standard tools are a common denominator, factorising (especially difference of two squares), sin⁡2x+cos⁡2x=1\sin^2 x + \cos^2 x = 1 and its rearrangements, and expanding brackets. For example: LHS =11−sin⁡x+11+sin⁡x=(1+sin⁡x)+(1−sin⁡x)(1−sin⁡x)(1+sin⁡x)=21−sin⁡2x=2cos⁡2x== \dfrac{1}{1-\sin x} + \dfrac{1}{1+\sin x} = \dfrac{(1+\sin x)+(1-\sin x)}{(1-\sin x)(1+\sin x)} = \dfrac{2}{1-\sin^2 x} = \dfrac{2}{\cos^2 x} = RHS. Each step is a recognised manipulation, no steps are skipped, and the final form matches the target exactly. If the result is printed (an 'AG' line) marks are typically awarded only for the working, so every manipulation must be visible.

4. Proof by mathematical induction: the five-part template (AHL)

Induction proves that a statement P(n)P(n) holds for all integers from a starting value onwards. Learn the layout by heart, because markschemes typically follow it closely.

(i) Base case (A1 or R1): evaluate both sides separately at the first value (usually n=1n=1, sometimes n=0n=0 or n=2n=2) and state they are equal, so P(1)P(1) is true.

(ii) Assumption (M1): 'Assume P(k)P(k) is true for some positive integer kk, that is ...' and write the full statement with nn replaced by kk. Writing 'let n=kn=k' or 'if n=kn=k' without the assumed statement usually scores zero here.

(iii) Inductive step set-up (M1): write what P(k+1)P(k+1) requires, then write the k+1k+1 expression and show explicitly where the assumption is substituted.

(iv) Algebra (A marks): manipulate until the expression is exactly the target with nn replaced by k+1k+1. Write the final line in terms of (k+1)(k+1) so the match is visible, for example ((k+1)−1)2(k+1)+1+2((k+1)-1)2^{(k+1)+1}+2.

(v) Conclusion (R1): 'P(1)P(1) is true, and P(k)P(k) true implies P(k+1)P(k+1) true; therefore P(n)P(n) is true for all positive integers nn by mathematical induction.' The sentence 'true by induction' alone does not earn this mark, and the mark is usually conditional on having scored the assumption and step marks.

5. The main induction families

Sums: P(k+1)P(k+1) is the sum to kk (replace it by the assumed closed form) plus the (k+1)(k+1)th term; then factorise towards the target. Divisibility: write the assumption as f(k)=dMf(k) = dM for some integer MM, express f(k+1)f(k+1) in terms of f(k)f(k) by splitting a coefficient, for example 5k+1−1=5⋅5k−1=5(5k−1)+4=5(4M)+4=4(5M+1)5^{k+1}-1 = 5\cdot 5^k - 1 = 5(5^k - 1) + 4 = 5(4M) + 4 = 4(5M+1), which is a multiple of 4. Inequalities: start from the k+1k+1 side, apply the assumption to obtain an inequality, then use an extra true fact (such as k≥1k \geq 1 or 2k>02^k > 0) to reach the k+1k+1 target; keep strict and weak inequalities exactly as stated. Derivatives: assume the formula for f(k)(x)f^{(k)}(x), differentiate once with the product or chain rule, and simplify to the formula with k+1k+1. Recursively defined sequences: substitute the assumed closed form for uku_k into the recurrence uk+1=g(uk)u_{k+1} = g(u_k) and simplify. In every family the base case must use the correct starting index, which is declared in the question. Beyond these five, De Moivre's theorem (AHL 1.14) for positive integer nn is also proved by induction, using the compound angle identities in the inductive step.

6. Proof by contradiction (AHL)

Assume the statement is false, deduce something impossible, and conclude the original statement must be true. The first line, the negation, carries a mark and must be exactly right: the negation of '2\sqrt{2} is irrational' is '2\sqrt{2} is rational', that is '2=pq\sqrt{2} = \frac{p}{q} with p,q∈Zp, q \in \mathbb{Z} and q≠0q \neq 0' (you may then add, as a separate permitted step, 'and we may take p,qp, q with no common factor'); the negation of a>ba > b is a≤ba \leq b (not a<ba < b); the negation of 'there are infinitely many' is 'there are finitely many'. Irrationality of 2\sqrt{2}: assume 2=pq\sqrt{2} = \frac{p}{q} with p,q∈Zp, q \in \mathbb{Z}, q≠0q \neq 0, and take the fraction in lowest terms; then p2=2q2p^2 = 2q^2 so p2p^2 is even, so pp is even (if pp were odd, p=2m+1p = 2m+1, then p2=4m2+4m+1p^2 = 4m^2 + 4m + 1 would be odd), p=2mp = 2m; then 4m2=2q24m^2 = 2q^2, q2=2m2q^2 = 2m^2, so by the same reasoning qq is even; pp and qq share the factor 2, contradicting lowest terms. Infinitely many primes: suppose the complete list is p1,p2,…,pnp_1, p_2, \ldots, p_n and let N=p1p2⋯pn+1N = p_1 p_2 \cdots p_n + 1; dividing NN by any pip_i leaves remainder 1, so no listed prime divides NN, yet N>1N > 1 has a prime factor, which is not in the list, a contradiction. Parity arguments are also common: if a,ba, b are integers then 2a+4b2a + 4b is even, so it cannot equal 1. Always end by naming the contradiction and restating the result.

7. Disproof by counterexample (AHL)

To show that a statement with 'for all' is not always true, exhibit one specific case for which it fails and show the calculation. For instance, the claim 'n2+n+41n^2 + n + 41 is prime for every positive integer nn' is false because n=41n = 41 gives 412+41+41=41×4341^2 + 41 + 41 = 41 \times 43, which is composite. The claim 'if f′(a)=0f'(a) = 0 then ff has a maximum or minimum at x=ax=a' is false for f(x)=x3f(x) = x^3 at a=0a=0. One counterexample settles the matter completely; several examples agreeing with a statement prove nothing, and a counterexample can never establish that a statement is true.

Formulas

Sn=n2(2u1+(n−1)d)S_n = \frac{n}{2}\left(2u_1 + (n-1)d\right) (often the statement to be proved by induction)in the booklet
Sn=u1(rn−1)r−1,  r≠1S_n = \frac{u_1(r^n - 1)}{r - 1}, \; r \neq 1 (often the statement to be proved by induction)in the booklet
Divisibility split: ak+1−1=a(ak−1)+(a−1)a^{k+1} - 1 = a(a^k - 1) + (a - 1)learn it
Even =2m= 2m, odd =2m+1= 2m+1, (2m+1)2=4m2+4m+1(2m+1)^2 = 4m^2 + 4m + 1learn it
Negation of a>ba > b is a≤ba \leq b; negation of 'irrational' is 'rational': =pq= \frac{p}{q} with p,q∈Zp, q \in \mathbb{Z}, q≠0q \neq 0 (lowest terms is a further step)learn it
Closing statement: P(1)P(1) true and P(k)⇒P(k+1)P(k) \Rightarrow P(k+1), so P(n)P(n) true for all n∈Z+n \in \mathbb{Z}^+ by inductionlearn it

Worked examples

Example 1

Prove that the sum of the squares of any two consecutive odd integers is 2 more than a multiple of 8.

Solution
  1. Represent the integers generally: let the two consecutive odd integers be 2n−12n - 1 and 2n+12n + 1, where n∈Zn \in \mathbb{Z}.
  2. Form the sum of squares: (2n−1)2+(2n+1)2=(4n2−4n+1)+(4n2+4n+1)(2n-1)^2 + (2n+1)^2 = (4n^2 - 4n + 1) + (4n^2 + 4n + 1).
  3. Simplify: =8n2+2= 8n^2 + 2.
  4. Give the reason: since nn is an integer, n2n^2 is an integer and so 8n28n^2 is a multiple of 8.
  5. Close: therefore the sum of the squares of two consecutive odd integers is 8n2+28n^2 + 2, which is 2 more than a multiple of 8, as required.

Answer: (2n−1)2+(2n+1)2=8n2+2(2n-1)^2 + (2n+1)^2 = 8n^2 + 2, which is 2 more than the multiple of 8 given by 8n28n^2. QED.

Example 2

Prove by mathematical induction that ∑r=1nr⋅2r=(n−1)2n+1+2\displaystyle\sum_{r=1}^{n} r \cdot 2^r = (n-1)2^{n+1} + 2 for all positive integers nn.

Solution
  1. Let P(n)P(n) be the statement ∑r=1nr⋅2r=(n−1)2n+1+2\sum_{r=1}^{n} r \cdot 2^r = (n-1)2^{n+1} + 2.
  2. Base case n=1n = 1: LHS =1⋅21=2= 1 \cdot 2^1 = 2; RHS =(1−1)22+2=0+2=2= (1-1)2^2 + 2 = 0 + 2 = 2. LHS == RHS, so P(1)P(1) is true.
  3. Assume P(k)P(k) is true for some positive integer kk, that is ∑r=1kr⋅2r=(k−1)2k+1+2\sum_{r=1}^{k} r \cdot 2^r = (k-1)2^{k+1} + 2.
  4. Consider n=k+1n = k+1: ∑r=1k+1r⋅2r=∑r=1kr⋅2r+(k+1)2k+1\sum_{r=1}^{k+1} r \cdot 2^r = \sum_{r=1}^{k} r \cdot 2^r + (k+1)2^{k+1}.
  5. Use the assumption: =(k−1)2k+1+2+(k+1)2k+1= (k-1)2^{k+1} + 2 + (k+1)2^{k+1}.
  6. Factorise: =2k+1[(k−1)+(k+1)]+2=2k+1(2k)+2=k⋅2k+2+2= 2^{k+1}\left[(k-1) + (k+1)\right] + 2 = 2^{k+1}(2k) + 2 = k \cdot 2^{k+2} + 2.
  7. Write in the target form: =((k+1)−1) 2(k+1)+1+2= ((k+1) - 1)\,2^{(k+1)+1} + 2, which is P(k+1)P(k+1).
  8. Conclusion: P(1)P(1) is true, and P(k)P(k) true implies P(k+1)P(k+1) true; therefore P(n)P(n) is true for all positive integers nn by mathematical induction.

Answer: The identity ∑r=1nr⋅2r=(n−1)2n+1+2\sum_{r=1}^{n} r \cdot 2^r = (n-1)2^{n+1} + 2 holds for all n∈Z+n \in \mathbb{Z}^+.

Example 3

Prove by contradiction that sin⁡x+cos⁡x>1\sin x + \cos x > 1 for all xx with 0<x<π20 < x < \dfrac{\pi}{2}.

Solution
  1. State the negation: assume there exists xx with 0<x<π20 < x < \frac{\pi}{2} such that sin⁡x+cos⁡x≤1\sin x + \cos x \leq 1.
  2. Key deduction about signs: for 0<x<π20 < x < \frac{\pi}{2} both sin⁡x>0\sin x > 0 and cos⁡x>0\cos x > 0, so sin⁡x+cos⁡x>0\sin x + \cos x > 0. Both sides of the assumed inequality are positive, so squaring preserves it.
  3. Square: (sin⁡x+cos⁡x)2≤1(\sin x + \cos x)^2 \leq 1, so sin⁡2x+2sin⁡xcos⁡x+cos⁡2x≤1\sin^2 x + 2\sin x \cos x + \cos^2 x \leq 1.
  4. Use sin⁡2x+cos⁡2x=1\sin^2 x + \cos^2 x = 1: 1+2sin⁡xcos⁡x≤11 + 2\sin x\cos x \leq 1, hence sin⁡xcos⁡x≤0\sin x \cos x \leq 0.
  5. Identify the contradiction: but sin⁡x>0\sin x > 0 and cos⁡x>0\cos x > 0 on this interval, so sin⁡xcos⁡x>0\sin x \cos x > 0. This contradicts sin⁡xcos⁡x≤0\sin x \cos x \leq 0.
  6. Conclude: the assumption is false, therefore sin⁡x+cos⁡x>1\sin x + \cos x > 1 for all 0<x<π20 < x < \frac{\pi}{2}, as required.

Answer: Assuming sin⁡x+cos⁡x≤1\sin x + \cos x \leq 1 leads to sin⁡xcos⁡x≤0\sin x \cos x \leq 0, impossible on 0<x<π20 < x < \frac{\pi}{2}; hence sin⁡x+cos⁡x>1\sin x + \cos x > 1. QED.

Can you...

  • Lay out a direct LHS to RHS proof of an algebraic or trigonometric identity without operating on both sides, ending with a closing statement?
  • Write the five induction components (base case, assumption, step, algebra, conclusion) in wording that typically earns A1, M1, M1, A1, R1?
  • Handle each induction family: add the next term in a sum, split a coefficient for divisibility, chain inequalities, differentiate an assumed kkth derivative, substitute into a recurrence?
  • Write the correct negation for 'irrational', 'infinitely many' and strict or weak inequalities, and reproduce the 2\sqrt{2} and infinitely-many-primes proofs?
  • Choose and verify a specific counterexample, showing the calculation that makes the statement fail?

Common errors

  • Base case shown as a single number or at the wrong index. Evaluate LHS and RHS separately at the starting value given in the question and state that they are equal.
  • Writing 'let n=kn = k' or 'if n=kn = k is true' instead of assuming. Write 'Assume P(k)P(k) is true for some positive integer kk' followed by the full statement with kk in place of nn; the M1 is usually lost otherwise.
  • Proving the k+1k+1 case from scratch or never showing where the assumption is used. Write the k+1k+1 expression, then substitute the assumed kk result on its own clearly labelled line.
  • Finishing with 'true by induction'. The R1 needs the complete sentence: true for n=1n=1, true for kk implies true for k+1k+1, so true for all positive integers nn.
  • Negating an inequality wrongly in a contradiction proof, for example writing a<ba < b as the opposite of a>ba > b. The negation of a>ba > b is a≤ba \leq b; write it down as the first line.
  • Offering numerical checks as a proof of a general statement. Examples can suggest or disprove a claim but can never prove it; use algebra with general integers such as 2m+12m+1.

Original questions and notes written by Pietro Meloni, PhD, from the IB syllabus. Not endorsed by or affiliated with the International Baccalaureate Organization. Found a mistake? Please tell me privately at pietro@pietromeloni.com. More questions on this topic: Number and algebra practice.

Find out what is costing the marks.

One to one, online, on Google Meet.

Book a first session