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
Not in the bookletProof by contradiction
Not in the bookletDisproof by counterexample
Not in the bookletMathematical induction
Not in the bookletEven and odd integers
is even and is odd, for an integer
Not in the bookletA common induction target: the sum of the first positive integers
Not in the bookletA common induction target: the sum of the first cubes
Not in the bookletDe Moivre's theorem, proved by induction for positive integers
In the bookletWhich 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 has | Use | Notes |
|---|---|---|
| A claim about even numbers, odd numbers or multiples, to be shown true | A direct proof with and | Use letters for general integers, never a particular number |
| An "if then " statement where it is easier to start from the end | Prove the contrapositive: if not then not | The two statements are equivalent, so proving one proves the other |
| A claim that a number is irrational, or that something is impossible | Proof by contradiction | Assume the opposite, reach something impossible, then say the assumption is false |
| A claim that should hold in every case but may not | A counterexample, then an explanation of why it fails | Naming 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 inequality | Mathematical induction | Base case, hypothesis, inductive step, then a conclusion that names all three |
| A request to verify the base case | Substitute the first value into both sides and compare | Both sides must be worked out and shown equal |
| A divisibility result to be proved by induction | Write the expression for as the expression for plus a multiple of the divisor | The 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 and an odd integer , where is an integer. Using letters makes the argument cover every case.
e.g. is even and 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 " for every integer " fails for , because , which is not greater than .
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 is even then is even" has contrapositive "if is odd then 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 is irrational, assume in lowest terms. Then makes even, and then is also even, which contradicts lowest terms.
Worked example, step by step
The question No calculator needed [5 marks]
Prove by contradiction that is irrational.
Worked solution: worked example
Answer: Assuming in its lowest terms forces both and to be multiples of , which is impossible, so is irrational.
Step 1 - Assume the opposite.
Suppose that is rational. Then for integers and with , where the fraction is in its lowest terms, so and have no common factor greater than . M1 - Assume with and 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 , so So is a multiple of . Since is prime and divides , divides . A1 - , so is a multiple of
Why? A prime that divides a product divides at least one of its factors, and here every factor is . This is the fact the argument depends on, so state it.
Step 3 - Substitute for .
Write for an integer . Then , so M1 - Substitute to obtain
Why? Replacing by a multiple of moves the factor of on to the other side, which is how the same reasoning can be used for .
Step 4 - Show that is a multiple of .
So is a multiple of , and for the same reason as before divides . A1 - is a multiple of
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 and are multiples of , which contradicts the assumption that is in its lowest terms. The assumption was therefore false, so is irrational. R1 - Both have a factor , which contradicts lowest terms, so 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.
M1 Assume with and integers with no common factor
A1 , so is a multiple of
M1 Substitute to obtain
A1 is a multiple of
R1 Both have a factor , which contradicts lowest terms, so 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.
Worked solution: practice question 1
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 shows nothing about or any other value - a direct proof needs general variables (like , , or ), 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 then " is "if not then not " - negating only one part, or reversing the implication without negating (which gives the converse instead), proves nothing about the original statement.
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 and use that assumption to prove it for . 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 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 cubes. In the inductive step, add the th term to the sum for .
Divisibility
Write the expression for as the expression for plus a multiple of the divisor, then use the hypothesis on the first part.
De Moivre's theorem
Induction proves for positive integers . 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 in the range, found by substituting that value into both sides.
e.g. To prove , take : the left side is and the right side is .
What is the inductive hypothesis?
The inductive hypothesis is the assumption that the statement is true for , where is some positive integer in the range. You are not proving it; you are using it.
e.g. Assume that .
What is the inductive step?
The inductive step shows that if the statement is true for , then it is true for . It must use the hypothesis.
e.g. .
How do you write the conclusion?
State that the base case is true, that truth for implies truth for , and that the statement is therefore true for all in the range by mathematical induction. A marks-earning proof needs all of these parts.
e.g. True for ; if true for then true for ; hence true for all by mathematical induction.
Worked example, step by step
The question No calculator needed [5 marks]
Prove by mathematical induction that is divisible by for all positive integers .
Worked solution: worked example
Answer: The statement is proved for all positive integers by mathematical induction.
Step 1 - Check the base case.
When , , which is divisible by . So the statement is true for . A1 - , divisible by , when
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 , where is a positive integer: M1 - Assume the statement is true for ,
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 " as turns the words into algebra you can use.
Step 3 - Set up the case .
Write as and use the hypothesis in the form : M1 - Write as and replace using the hypothesis
Why? The expression for has to be linked to the expression for . This is the step that uses the assumption.
Step 4 - Simplify to a multiple of .
Expanding, Since is an integer, is divisible by , which is the statement with replaced by . A1 -
Why? To show divisibility by , write the result as times something and say that the something is an integer.
Step 5 - Write the conclusion.
The statement is true for . If it is true for , then it is true for . Therefore, by mathematical induction, the statement is true for all positive integers . R1 - Conclusion naming the base case, the inductive step and all positive integers
Why? The conclusion has to mention the base case, the inductive step and the range of . A line such as "so it is true" is not enough.
A1 , divisible by , when
M1 Assume the statement is true for ,
M1 Write as and replace using the hypothesis
A1
R1 Conclusion naming the base case, the inductive step and all positive integers
Now you try: enter your answers to be marked
Worked solution: practice question 1
Worked solution: practice question 2
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 . The inductive step must show the case by substituting the assumed 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 (in the stated range) by mathematical induction.
Syllabus content covered
| Code | Syllabus content |
|---|---|
| AHL1.15 | Proof 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.15 | Proof by contradiction. Examples: Irrationality of ; irrationality of the cube root of 5; Euclid's proof of an infinite number of prime numbers; if is a rational number and is an irrational number, then is an irrational number. |
| AHL1.15 | Use 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 (the inductive hypothesis), show it must then hold for , and conclude that it holds for all 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 to - 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 is prime holds for , and , but it fails for .
What if the statement starts at a value other than ?
The base case is the first value in the stated range. A statement for needs the base case , and the conclusion covers all . For , the base case is .
How do I prove that the sum of two odd integers is even?
Write the integers as and . Their sum is , which is twice an integer, so it is even.
How do I prove a divisibility result by induction?
Write the expression for in terms of the expression for plus a multiple of the divisor. To show is divisible by , assume ; then .
How do I write a counterexample properly?
State a specific value, calculate what the statement predicts, and say that it fails. To disprove "if is prime then is prime", take : is prime but is not.
Why am I allowed to assume the statement for ?
You are not claiming it is true; you are proving an implication, that truth for leads to truth for . 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.