IB Mathematics: Analysis and Approaches · Topic 1 · Number and algebra
1.15 Proof by induction and contradiction
Prove statements by induction, identify the base case and inductive step, and use contradiction to rule out a statement.
1/5Induction proves a statement for every positive integer
- Induction proves a statement for every positive integer
- The inductive step assumes the statement is true for some k
- Induction also proves divisibility and inequality statements
- Proof by contradiction assumes the opposite and finds an impossibility
- A single counterexample disproves a general claim
- Check your recall
- Practice: 10 questions
Part 1 of 5: Induction proves a statement for every positive integer
Picture a long row of dominoes. If the first falls, and each falling domino knocks over the next, then all of them fall. Mathematical induction works the same way for a statement about .
A proof has four parts.
- Base case: show the statement is true for the first value of , usually .
- Assumption: suppose it is true for .
- Inductive step: use that assumption to show it is true for .
- Conclusion: state that it is true for all positive integers .
Key terms · tap one for its definition
mathematical induction
Mathematical induction is a method of proving a statement for all integers by proving a base case and an inductive step.
base case
The base case is the check that the statement holds for the smallest value of in the claim.
inductive step
The inductive step is the proof that truth for forces truth for .
Part 2 of 5: The inductive step assumes the statement is true for some k
Now watch the four parts work on a real statement. The assumption that the statement is true for is the inductive hypothesis. You may use it freely. You may not assume anything about .
Write down the target statement for before you start. It shows what the final line must look like.
The step is a conditional claim: if the statement holds for , then it holds for . It does not claim the statement is true for .
Worked example
Prove a sum formula by induction
- Base case : the left side is 1 and the right side is . They match.
- Assume true for : .
- For , add the next term: .
- Factorise: .
- This is the statement with .
Answer: The statement is true for , and truth for gives truth for . By induction it holds for all positive integers .
Key term
inductive hypothesis
The inductive hypothesis is the assumption that the statement is true for , where is a particular positive integer.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 3 of 5: Induction also proves divisibility and inequality statements
Sums are not the only use. Induction also handles claims such as ‘ is divisible by 6’. Here you write the expression for in terms of the one for .
Worked example
Prove a divisibility statement
- Base case : , which is divisible by 6.
- Assume for some integer .
- Then .
- Substitute: .
- This is a multiple of 6, so the statement holds for .
Answer: The base case holds and the step works, so is divisible by 6 for all positive integers .
The base case need not be . If a claim starts at , check instead. The conclusion then covers . For an inequality, the step usually compares one side with a simpler expression.
Part 4 of 5: Proof by contradiction assumes the opposite and finds an impossibility
Induction handles statements about integers one step at a time. Some claims need another route. A proof by contradiction starts by assuming the claim is false. You then follow correct logic until you reach something impossible.
Correct logic cannot lead to an impossibility, so the assumption must be wrong. The claim is therefore true. In the same way, any statement that leads to an impossibility is false. The classic target is to show that is an irrational number.
Worked example
Prove that the square root of 2 is irrational
- Assume the opposite: , where and are integers with no common factor.
- Square and rearrange: , so is even.
- If is even then is even, so write .
- Then , so and is even.
- Now and are both even, so they share the factor 2. This contradicts the assumption.
Answer: The assumption is false, so is irrational.
Notice the pattern. Valid steps led from the assumption to a clash with the choice of lowest terms. That clash is the contradiction.
Key terms · tap one for its definition
proof by contradiction
A proof by contradiction assumes the negation of a statement and shows that this assumption leads to an impossible result.
irrational number
An irrational number is a real number that cannot be written as with integers and , where .

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 5 of 5: A single counterexample disproves a general claim
Sometimes a claim is simply false. You can then stop proving and look for one case that breaks it. A counterexample is exactly such a case.
Take the claim that is prime for every positive integer . It works for , 2 and 3, and for many more values. But gives , which is not prime. One failure is enough.
Three methods compared
- Method
- Induction
- Used for
- truth for all integers from a start value
- Main idea
- base case, then step from to
- Method
- Contradiction
- Used for
- proving a claim by ruling out its opposite
- Main idea
- assume the opposite, reach an impossibility
- Method
- Counterexample
- Used for
- showing a claim is false
- Main idea
- find one case where it fails
Choose the method from the wording of the task. A request to prove a claim for all usually points to induction. A request to show a claim is false points to a counterexample.
Key term
counterexample
A counterexample is a single case that meets the conditions of a general claim but makes its conclusion false.
Check your recall[14 marks]
6 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.State[2 marks]
State the two parts of a proof by induction that must both be shown.
Show mark schemeHide mark scheme
Model answer
The base case must be shown to be true. The inductive step must show that truth for gives truth for .
- 1 mark for stating that the base case holds
- 1 mark for stating that truth for implies truth for
- 2.Identify[2 marks]
Identify the inductive hypothesis when proving by induction.
Show mark schemeHide mark scheme
Model answer
Assume the statement is true for , that is for some positive integer .
- 1 mark for stating that the assumption is made for
- 1 mark for writing the statement as
- 3.Explain[2 marks]
Explain why checking the statement for the first five values of does not prove it for all .
Show mark schemeHide mark scheme
Model answer
A finite number of checks cannot cover every positive integer. A counterexample may appear for a larger , whereas induction covers every value through the inductive step.
- 1 mark for stating that checking finitely many cases does not cover every
- 1 mark for stating that a later case could still fail, or that induction is needed to cover all
- 4.Outline[3 marks]
Outline the steps of a proof by contradiction.
Show mark schemeHide mark scheme
Model answer
Assume the statement is false. Use correct logic to reach a result that is impossible. Conclude that the assumption was wrong, so the statement is true.
- 1 mark for assuming the opposite of the statement
- 1 mark for deducing an impossible result by correct logic
- 1 mark for concluding that the assumption is false so the original statement is true
- 5.Write down[2 marks]
Write down a counterexample to the claim that for every positive integer .
Show mark schemeHide mark scheme
Model answer
Take . Then and , and is false.
- 1 mark for choosing
- 1 mark for showing that is not greater than 1
- 6.Deduce[3 marks]
Given that is divisible by 6, deduce that is divisible by 6.
Show mark schemeHide mark scheme
Model answer
Write . Then , which is a multiple of 6.
- 1 mark for writing
- 1 mark for substituting to obtain
- 1 mark for concluding that the expression is divisible by 6

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
EasyState[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumDeduce[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumDetermine[2 marks]
Show answer and explanation
Answer: A · Worked explanation
MediumDetermine[2 marks]
Show answer and explanation
Answer: A · Worked explanation
HardDetermine[2 marks]
Show answer and explanation
Answer: A · Worked explanation
HardDetermine[2 marks]
Show answer and explanation
Answer: A · Worked explanation
HardIdentify[2 marks]
Show answer and explanation
Answer: A · Worked explanation