Proof AA HL

A proof is a chain of logical steps from what is given to what is claimed, and every step has to be justified. Use a direct proof when you can work forward from general assumptions, a proof by contradiction when the opposite of the claim leads to something impossible, a counterexample to show a claim is not always true, and mathematical induction for a statement about every integer from a starting value. Write each argument in full, using letters rather than one example, and end with a conclusion that says what has been shown.

Formulas at a glance

The proof structures are patterns of argument, not formulas, so none of them is in the formula booklet. The two sums that are common targets of induction are not listed there either. De Moivre's theorem is in the booklet, and induction is how it is proved for positive integers.

Direct proof

general case→algebra→stated result\text{general case}\to\text{algebra}\to\text{stated result}

Not in the booklet

Proof by contradiction

assume the negation→contradiction→conclude\text{assume the negation}\to\text{contradiction}\to\text{conclude}

Not in the booklet

Disproof by counterexample

failing case→explain why it fails\text{failing case}\to\text{explain why it fails}

Not in the booklet

Mathematical induction

base case→hypothesis→inductive step→conclusion\text{base case}\to\text{hypothesis}\to\text{inductive step}\to\text{conclusion}

Not in the booklet

Even and odd integers

2m2m is even and 2m+12m+1 is odd, for an integer mm

Not in the booklet

A common induction target: the sum of the first nn positive integers

∑r=1nr=n(n+1)2\displaystyle\sum_{r=1}^{n} r=\dfrac{n(n+1)}{2}

Not in the booklet

A common induction target: the sum of the first nn cubes

∑r=1nr3=n2(n+1)24\displaystyle\sum_{r=1}^{n} r^3=\dfrac{n^2(n+1)^2}{4}

Not in the booklet

De Moivre's theorem, proved by induction for positive integers nn

(rcisθ)n=rncis(nθ)(r\,\text{cis}\,\theta)^n=r^n\,\text{cis}(n\theta)

In the booklet

Which method to use

Read the wording of the claim first. "For all", "prove that" and "show that" point to a proof; "not always true" points to a counterexample; a statement about every positive integer points to induction.

The question hasUseNotes
A claim about even numbers, odd numbers or multiples, to be shown trueA direct proof with 2m2m and 2m+12m+1Use letters for general integers, never a particular number
An "if PP then QQ" statement where it is easier to start from the endProve the contrapositive: if not QQ then not PPThe two statements are equivalent, so proving one proves the other
A claim that a number is irrational, or that something is impossibleProof by contradictionAssume the opposite, reach something impossible, then say the assumption is false
A claim that should hold in every case but may notA counterexample, then an explanation of why it failsNaming the value is not enough: show the claim fails for it
A statement about every integer from a starting value, such as a sum, a divisibility result or an inequalityMathematical inductionBase case, hypothesis, inductive step, then a conclusion that names all three
A request to verify the base caseSubstitute the first value into both sides and compareBoth sides must be worked out and shown equal
A divisibility result to be proved by inductionWrite the expression for k+1k+1 as the expression for kk plus a multiple of the divisorThe first part is replaced using the hypothesis

Section 1 of 2 AHL1.15

Direct proof and disproof

A direct proof starts from general assumptions and reasons forward, using algebra, to reach the statement to be proved. A proof by contradiction assumes the statement is false and shows that this is impossible. To disprove a statement that claims to hold in every case, one counterexample is enough, provided you show that it really breaks the statement.

Setting out each structure

The three structures are in the formulas at the top of the page. This is what each one needs from you.

Direct proof

Start from arbitrary integers or reals, never a specific number, and work forward until you arrive at exactly what was asked for. End with a sentence that says what has been shown.

Proof by contradiction

Begin with "Assume that" followed by the exact opposite of the claim. Show that this forces something impossible, then state that the assumption is false, so the claim is true.

Disproof by counterexample

Name one case, work out what the claim predicts for it, and show that the claim fails. The explanation is part of the answer: a value on its own earns no credit.

A statement about every integer from a starting value is often better suited to mathematical induction.

Key terms

How do you represent even and odd integers in a proof?

An even integer can be written 2m2m and an odd integer 2m+12m+1, where mm is an integer. Using letters makes the argument cover every case.

e.g. 14=2(7)14=2(7) is even and 15=2(7)+115=2(7)+1 is odd.

What is a counterexample?

A counterexample is a single case in which a general statement is false. One counterexample is enough to disprove "for all", and you must show clearly that the case fails.

e.g. The claim "n2>nn^2>n for every integer nn" fails for n=1n=1, because 12=11^2=1, which is not greater than 11.

What is the contrapositive?

The contrapositive of "if P then Q" is "if not Q then not P". The two statements are logically equivalent, so proving one proves the other.

e.g. "If n2n^2 is even then nn is even" has contrapositive "if nn is odd then n2n^2 is odd".

What are the steps in a proof by contradiction?

Assume the opposite of what you want to prove, reason logically until you reach something impossible, then state that the assumption must be false. The original statement is then true.

e.g. To show 2\sqrt{2} is irrational, assume 2=pq\sqrt{2}=\dfrac{p}{q} in lowest terms. Then p2=2q2p^2=2q^2 makes pp even, and then qq is also even, which contradicts lowest terms.

Worked example, step by step

The question No calculator needed [5 marks]

Prove by contradiction that 53\sqrt[3]{5} is irrational.

Worked solution: worked example

Answer: Assuming 53=pq\sqrt[3]{5}=\dfrac{p}{q} in its lowest terms forces both pp and qq to be multiples of 55, which is impossible, so 53\sqrt[3]{5} is irrational.

Step 1 - Assume the opposite.

Suppose that 53\sqrt[3]{5} is rational. Then 53=pq\sqrt[3]{5}=\dfrac{p}{q} for integers pp and qq with q≠0q\neq0, where the fraction is in its lowest terms, so pp and qq have no common factor greater than 11. M1 - Assume 53=pq\sqrt[3]{5}=\dfrac{p}{q} with pp and qq integers with no common factor

Why? A proof by contradiction begins by assuming the negation of the claim. The negation of "irrational" is "rational", and any rational number can be written as a fraction in its lowest terms.

Step 2 - Cube both sides.

Cubing gives 5=p3q35=\dfrac{p^3}{q^3}, so p3=5q3.p^3=5q^3. So p3p^3 is a multiple of 55. Since 55 is prime and 55 divides p×p×pp\times p\times p, 55 divides pp. A1 - p3=5q3p^3=5q^3, so pp is a multiple of 55

Why? A prime that divides a product divides at least one of its factors, and here every factor is pp. This is the fact the argument depends on, so state it.

Step 3 - Substitute for pp.

Write p=5sp=5s for an integer ss. Then 125s3=5q3125s^3=5q^3, so q3=25s3=5(5s3).q^3=25s^3=5(5s^3). M1 - Substitute p=5sp=5s to obtain q3=25s3q^3=25s^3

Why? Replacing pp by a multiple of 55 moves the factor of 55 on to the other side, which is how the same reasoning can be used for qq.

Step 4 - Show that qq is a multiple of 55.

So q3q^3 is a multiple of 55, and for the same reason as before 55 divides qq. A1 - qq is a multiple of 55

Why? The same prime fact is used a second time, so it does not need to be proved again: refer back to it.

Step 5 - State the contradiction and conclude.

Both pp and qq are multiples of 55, which contradicts the assumption that pq\dfrac{p}{q} is in its lowest terms. The assumption was therefore false, so 53\sqrt[3]{5} is irrational. R1 - Both have a factor 55, which contradicts lowest terms, so 53\sqrt[3]{5} is irrational

Why? The conclusion must name the contradiction and say that the assumption is false. Stopping at "this is a contradiction" without a final sentence loses the last mark.

Marks (5):
M1 Assume 53=pq\sqrt[3]{5}=\dfrac{p}{q} with pp and qq integers with no common factor
A1 p3=5q3p^3=5q^3, so pp is a multiple of 55
M1 Substitute p=5sp=5s to obtain q3=25s3q^3=25s^3
A1 qq is a multiple of 55
R1 Both have a factor 55, which contradicts lowest terms, so 53\sqrt[3]{5} is irrational

Now you try: enter your answers to be marked

These are real practice questions. Type your answer in each box and press Mark it. The worked solution and mark scheme appear straight away, and your first attempt is the one that counts. Use the keyboard for powers, roots and trig, and the working box for your notes.

1
Medium
Calculator
[4 marks]
The claim is 'n2+n+11n^2+n+11 is prime for all positive integers nn'. By testing values, find a counterexample.
(a)(i) State the smallest positive integer value of nn that is a counterexample.
[1]
(a)(ii) State the value of n2+n+11n^2+n+11 at that nn.
[1]
(b)(i) Find n2+n+11n^2+n+11 at n=1.n=1.
[1]
(b)(ii) Confirm it is prime.
[1]
Fractions & powers
Other

Worked solution: practice question 1

2
Medium
No calc
[5 marks]
Let nn be an integer. An odd number can be written as 2n+12n+1.
(a) Expand (2n+1)2(2n+1)^{2}.
[2]
(b) Write (2n+1)2−1(2n+1)^{2}-1 in the form 8m8m, where mm is an expression in nn. Find mm.
[2]
(c) Select the reason that mm is an integer for every integer nn.
[1]
Fractions & powers
Other

Worked solution: practice question 2

Your score so far: 0 out of 9 marks

Common mistakes

  • "Proving" a general statement with one example. Checking that a claim works for n=4n=4 shows nothing about n=5n=5 or any other value - a direct proof needs general variables (like 2a2a, 2b2b, or 2k+12k+1), not a single number.
  • Asserting a counterexample instead of checking it. Naming a value that you believe breaks a statement isn't enough - the disproof mark comes from actually substituting it in and showing, in full, that it fails.
  • Forming the contrapositive incorrectly. The contrapositive of "if PP then QQ" is "if not QQ then not PP" - negating only one part, or reversing the implication without negating (which gives the converse instead), proves nothing about the original statement.

Try some questions on direct proof and disproof

Section 2 of 2 AHL1.15

Mathematical induction

Proof by mathematical induction shows that a statement is true for every integer from a starting value onwards. First show it holds for the starting value, then assume it holds for n=kn=k and use that assumption to prove it for n=k+1n=k+1. A closing sentence links these steps to a conclusion for all values in the stated range.

What induction usually proves

The four stages are in the formulas at the top of the page. These are the statements that most often need them.

Sums

The sum of the first nn positive integers follows from the arithmetic series formula in the booklet, but you may still be asked to prove it by induction, as you may for the sum of the first nn cubes. In the inductive step, add the (k+1)(k+1)th term to the sum for n=kn=k.

Divisibility

Write the expression for n=k+1n=k+1 as the expression for n=kn=k plus a multiple of the divisor, then use the hypothesis on the first part.

De Moivre's theorem

Induction proves (rcisθ)n=rncis(nθ)(r\,\text{cis}\,\theta)^n=r^n\,\text{cis}(n\theta) for positive integers nn. The theorem is in the booklet and is used on the complex numbers page.

Key terms

What is the base case?

The base case is a check that the statement is true for the first value of nn in the range, found by substituting that value into both sides.

e.g. To prove 1+3+5+⋯+(2n−1)=n21+3+5+\dots+(2n-1)=n^2, take n=1n=1: the left side is 11 and the right side is 12=11^2=1.

What is the inductive hypothesis?

The inductive hypothesis is the assumption that the statement is true for n=kn=k, where kk is some positive integer in the range. You are not proving it; you are using it.

e.g. Assume that 1+3+5+⋯+(2k−1)=k21+3+5+\dots+(2k-1)=k^2.

What is the inductive step?

The inductive step shows that if the statement is true for n=kn=k, then it is true for n=k+1n=k+1. It must use the hypothesis.

e.g. 1+3+⋯+(2k−1)+(2k+1)=k2+(2k+1)=(k+1)21+3+\dots+(2k-1)+(2k+1)=k^2+(2k+1)=(k+1)^2.

How do you write the conclusion?

State that the base case is true, that truth for n=kn=k implies truth for n=k+1n=k+1, and that the statement is therefore true for all nn in the range by mathematical induction. A marks-earning proof needs all of these parts.

e.g. True for n=1n=1; if true for n=kn=k then true for n=k+1n=k+1; hence true for all n∈Z+n\in\mathbb{Z}^+ by mathematical induction.

Worked example, step by step

The question No calculator needed [5 marks]

Prove by mathematical induction that 7n+27^n+2 is divisible by 33 for all positive integers nn.

Worked solution: worked example

Answer: The statement is proved for all positive integers nn by mathematical induction.

Step 1 - Check the base case.

When n=1n=1, 71+2=9=3×37^1+2=9=3\times3, which is divisible by 33. So the statement is true for n=1n=1. A1 - 7+2=97+2=9, divisible by 33, when n=1n=1

Why? The base case is a check of the statement at the first value. It shows that the chain of reasoning has somewhere to start.

Step 2 - Write the inductive hypothesis.

Assume that the statement is true for n=kn=k, where kk is a positive integer: 7k+2=3mfor some integer m.7^k+2=3m\quad\text{for some integer } m. M1 - Assume the statement is true for n=kn=k, 7k+2=3m7^k+2=3m

Why? The words "assume" or "suppose" matter. You are not claiming this is true, only using it as a starting point in the next step. Writing "divisible by 33" as 3m3m turns the words into algebra you can use.

Step 3 - Set up the case n=k+1n=k+1.

Write 7k+17^{k+1} as 7×7k7\times7^k and use the hypothesis in the form 7k=3m−27^k=3m-2: 7k+1+2=7×7k+2=7(3m−2)+2.7^{k+1}+2=7\times7^k+2=7(3m-2)+2. M1 - Write 7k+1+27^{k+1}+2 as 7×7k+27\times7^k+2 and replace 7k7^k using the hypothesis

Why? The expression for n=k+1n=k+1 has to be linked to the expression for n=kn=k. This is the step that uses the assumption.

Step 4 - Simplify to a multiple of 33.

Expanding, 7(3m−2)+2=21m−14+2=21m−12=3(7m−4).7(3m-2)+2=21m-14+2=21m-12=3(7m-4). Since 7m−47m-4 is an integer, 7k+1+27^{k+1}+2 is divisible by 33, which is the statement with nn replaced by k+1k+1. A1 - 3(7m−4)3(7m-4)

Why? To show divisibility by 33, write the result as 33 times something and say that the something is an integer.

Step 5 - Write the conclusion.

The statement is true for n=1n=1. If it is true for n=kn=k, then it is true for n=k+1n=k+1. Therefore, by mathematical induction, the statement is true for all positive integers nn. R1 - Conclusion naming the base case, the inductive step and all positive integers nn

Why? The conclusion has to mention the base case, the inductive step and the range of nn. A line such as "so it is true" is not enough.

Marks (5):
A1 7+2=97+2=9, divisible by 33, when n=1n=1
M1 Assume the statement is true for n=kn=k, 7k+2=3m7^k+2=3m
M1 Write 7k+1+27^{k+1}+2 as 7×7k+27\times7^k+2 and replace 7k7^k using the hypothesis
A1 3(7m−4)3(7m-4)
R1 Conclusion naming the base case, the inductive step and all positive integers nn

Now you try: enter your answers to be marked

1
Easy
No calc
[2 marks]
Verify the base case (n=1)(n=1) of the statement ∑r=1nr=n(n+1)2\displaystyle\sum_{r=1}^{n}r=\tfrac{n(n+1)}{2}.
[2]
Fractions & powers
Other

Worked solution: practice question 1

2
Easy
No calc
[2 marks]
Verify the base case (n=1)(n=1) of ∑r=1nr3=n2(n+1)24\displaystyle\sum_{r=1}^{n}r^3=\tfrac{n^2(n+1)^2}{4}.
[2]
Fractions & powers
Other

Worked solution: practice question 2

3
Medium
No calc
[4 marks]
For positive integers nn, let P(n)\mathrm{P}(n) be the statement ∑r=1nr(r+1)=n(n+1)(n+2)3\displaystyle\sum_{r=1}^{n}r(r+1)=\dfrac{n(n+1)(n+2)}{3}.
(a) Find the common value of the two sides of P(1)\mathrm{P}(1).
[1]
(b) Assume that P(k)\mathrm{P}(k) is true for some positive integer kk. Then ∑r=1k+1r(r+1)=k(k+1)(k+2)3+(k+1)(k+2)=(k+1)(k+2)(k+m)3\displaystyle\sum_{r=1}^{k+1}r(r+1)=\dfrac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\dfrac{(k+1)(k+2)(k+m)}{3}. Find the value of mm.
[2]
(c) Select the conclusion that completes the proof by induction.
[1]
Fractions & powers
Other

Worked solution: practice question 3

Your score so far: 0 out of 8 marks

Common mistakes

  • 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 actually using the assumption for n=kn=k. The inductive step must show the n=k+1n=k+1 case by substituting the assumed n=kn=k result into the working - simply re-deriving the target formula from scratch earns no method credit.
  • Missing or vague conclusion. "So it's true" is not enough - the final line needs to reference that the base case holds, the inductive step is proven, and hence the statement is true for all nn (in the stated range) by mathematical induction.

Try some questions on mathematical induction

Syllabus content covered

CodeSyllabus content
AHL1.15Proof by mathematical induction. Proof should be incorporated throughout the course where appropriate. Mathematical induction links specifically to a wide variety of topics, for example complex numbers, differentiation, sums of sequences and divisibility.
AHL1.15Proof by contradiction. Examples: Irrationality of 3\sqrt{3}; irrationality of the cube root of 5; Euclid's proof of an infinite number of prime numbers; if aa is a rational number and bb is an irrational number, then a+ba+b is an irrational number.
AHL1.15Use of a counterexample to show that a statement is not always true. It is not sufficient to state the counterexample alone. Students must explain why their example is a counterexample.

Official IB source: Mathematics: analysis and approaches subject brief (PDF, ibo.org).

Quick questions

What is the difference between a direct proof and a proof by contradiction?

A direct proof starts from general assumptions and reasons forward, step by logical step, to the stated result. A proof by contradiction instead assumes the result is false, then shows that assumption leads to something impossible - which means the original result must be true after all.

What are the four stages of a proof by induction?

State and verify the base case, assume the statement holds for n=kn=k (the inductive hypothesis), show it must then hold for n=k+1n=k+1, and conclude that it holds for all nn in the stated range by the principle of mathematical induction.

How do you disprove a statement in IB Maths?

A general statement (one claimed to be true for all cases) is disproved by finding a single counterexample - one specific case where it fails - and clearly checking that the case really does break the statement.

Why can't you skip the base case in an induction proof?

The inductive step only shows that truth passes from n=kn=k to n=k+1n=k+1 - it never shows the statement is true anywhere on its own. Without a verified starting point there's nothing for that chain of implications to start from, so the whole proof has no foundation.

Why can't a proof be based on testing examples?

Examples only show a statement works for those cases, not for every case. The statement that every odd number greater than 11 is prime holds for 33, 55 and 77, but it fails for 9=3×39=3\times3.

What if the statement starts at a value other than n=1n=1?

The base case is the first value in the stated range. A statement for n≥3n\ge3 needs the base case n=3n=3, and the conclusion covers all n≥3n\ge3. For 2n>2n2^n>2n, the base case is 8>68>6.

How do I prove that the sum of two odd integers is even?

Write the integers as 2a+12a+1 and 2b+12b+1. Their sum is 2a+2b+2=2(a+b+1)2a+2b+2=2(a+b+1), which is twice an integer, so it is even.

How do I prove a divisibility result by induction?

Write the expression for n=k+1n=k+1 in terms of the expression for n=kn=k plus a multiple of the divisor. To show 5n−15^n-1 is divisible by 44, assume 5k−1=4m5^k-1=4m; then 5k+1−1=5(4m+1)−1=20m+4=4(5m+1)5^{k+1}-1=5(4m+1)-1=20m+4=4(5m+1).

How do I write a counterexample properly?

State a specific value, calculate what the statement predicts, and say that it fails. To disprove "if nn is prime then n+2n+2 is prime", take n=7n=7: 77 is prime but 7+2=9=3×37+2=9=3\times3 is not.

Why am I allowed to assume the statement for n=kn=k?

You are not claiming it is true; you are proving an implication, that truth for n=kn=k leads to truth for n=k+1n=k+1. Combined with the base case, this builds a chain from the first value to every later value.

Ready to practise properly?

Practice questions on every section, marked instantly like the real exam.