Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Mathematics: Analysis and Approaches
  3. ›1 Number and algebra
  4. ›1.15 Proof by induction and contradiction

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.

  • 5 min read
  • 5 parts
  • 10 questions
  • Draft
  • HL only
Start a Quick 5 on this topic→Jump to the 10 questions
1/5Induction proves a statement for every positive integer
  1. 1Induction proves a statement for every positive integer
  2. 2The inductive step assumes the statement is true for some k
  3. 3Induction also proves divisibility and inequality statements
  4. 4Proof by contradiction assumes the opposite and finds an impossibility
  5. 5A single counterexample disproves a general claim
  6. Check your recall
  7. Practice: 10 questions
1

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 nnn.

A proof has four parts.

  • Base case: show the statement is true for the first value of nnn, usually n=1n=1n=1.
  • Assumption: suppose it is true for n=kn=kn=k.
  • Inductive step: use that assumption to show it is true for n=k+1n=k+1n=k+1.
  • Conclusion: state that it is true for all positive integers nnn.

Exam tip

Always write the conclusion. Say that the base case holds, the step works, and so the statement is true for all nnn.

Key terms · tap one for its definition

mathematical induction

Mathematical induction is a method of proving a statement for all integers n≥n0n\ge n_0n≥n0​ 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 nnn in the claim.

inductive step

The inductive step is the proof that truth for n=kn=kn=k forces truth for n=k+1n=k+1n=k+1.

Part 1 done

2

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 n=kn=kn=k is the inductive hypothesis. You may use it freely. You may not assume anything about k+1k+1k+1.

Write down the target statement for n=k+1n=k+1n=k+1 before you start. It shows what the final line must look like.

The step is a conditional claim: if the statement holds for kkk, then it holds for k+1k+1k+1. It does not claim the statement is true for kkk.

Worked example

Prove a sum formula by induction

Prove that ∑r=1nr=n(n+1)2\sum_{r=1}^{n}r=\frac{n(n+1)}{2}∑r=1n​r=2n(n+1)​ for all positive integers nnn.
  1. 1
    Base case n=1n=1n=1: the left side is 1 and the right side is 1×22=1\frac{1\times2}{2}=121×2​=1. They match.
  2. 2
    Assume true for n=kn=kn=k: ∑r=1kr=k(k+1)2\sum_{r=1}^{k}r=\frac{k(k+1)}{2}∑r=1k​r=2k(k+1)​.
  3. 3
    For n=k+1n=k+1n=k+1, add the next term: ∑r=1k+1r=k(k+1)2+(k+1)\sum_{r=1}^{k+1}r=\frac{k(k+1)}{2}+(k+1)∑r=1k+1​r=2k(k+1)​+(k+1).
  4. 4
    Factorise: (k+1)(k2+1)=(k+1)(k+2)2(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}(k+1)(2k​+1)=2(k+1)(k+2)​.
  5. 5
    This is the statement with n=k+1n=k+1n=k+1.

Answer: The statement is true for n=1n=1n=1, and truth for n=kn=kn=k gives truth for n=k+1n=k+1n=k+1. By induction it holds for all positive integers nnn.

Common mistake

Do not assume the statement for n=k+1n=k+1n=k+1. That is exactly what the inductive step must prove.

Key term

inductive hypothesis

The inductive hypothesis is the assumption that the statement is true for n=kn=kn=k, where kkk is a particular positive integer.

Part 2 done

Quick check

One question on the part you just read

Easy

Identify the purpose of the base case in a proof by induction.
Show answer and explanation

Answer: A · Worked explanation

The base case checks the first value, so the chain of reasoning has a starting point. Assuming truth for n=kn=kn=k is the inductive hypothesis, and using it to reach n=k+1n=k+1n=k+1 is the inductive step. The base case does neither.
3

Part 3 of 5: Induction also proves divisibility and inequality statements

Sums are not the only use. Induction also handles claims such as ‘7n−17^n-17n−1 is divisible by 6’. Here you write the expression for n=k+1n=k+1n=k+1 in terms of the one for n=kn=kn=k.

Worked example

Prove a divisibility statement

Prove that 7n−17^n-17n−1 is divisible by 6 for all positive integers nnn.
  1. 1
    Base case n=1n=1n=1: 71−1=67^1-1=671−1=6, which is divisible by 6.
  2. 2
    Assume 7k−1=6m7^k-1=6m7k−1=6m for some integer mmm.
  3. 3
    Then 7k+1−1=7×7k−1=7(7k−1)+67^{k+1}-1=7\times7^k-1=7\left(7^k-1\right)+67k+1−1=7×7k−1=7(7k−1)+6.
  4. 4
    Substitute: 7(6m)+6=6(7m+1)7(6m)+6=6(7m+1)7(6m)+6=6(7m+1).
  5. 5
    This is a multiple of 6, so the statement holds for n=k+1n=k+1n=k+1.

Answer: The base case holds and the step works, so 7n−17^n-17n−1 is divisible by 6 for all positive integers nnn.

The base case need not be n=1n=1n=1. If a claim starts at n=4n=4n=4, check n=4n=4n=4 instead. The conclusion then covers n≥4n\ge4n≥4. For an inequality, the step usually compares one side with a simpler expression.

Exam tip

In divisibility proofs, write the assumption as an equation such as 7k−1=6m7^k-1=6m7k−1=6m. You can then substitute it directly.

Part 3 done

4

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 2\sqrt22​ is an irrational number.

Worked example

Prove that the square root of 2 is irrational

Prove that 2\sqrt22​ is irrational.
  1. 1
    Assume the opposite: 2=pq\sqrt2=\frac{p}{q}2​=qp​, where ppp and qqq are integers with no common factor.
  2. 2
    Square and rearrange: p2=2q2p^2=2q^2p2=2q2, so p2p^2p2 is even.
  3. 3
    If p2p^2p2 is even then ppp is even, so write p=2mp=2mp=2m.
  4. 4
    Then 4m2=2q24m^2=2q^24m2=2q2, so q2=2m2q^2=2m^2q2=2m2 and qqq is even.
  5. 5
    Now ppp and qqq are both even, so they share the factor 2. This contradicts the assumption.

Answer: The assumption is false, so 2\sqrt22​ 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 pq\frac{p}{q}qp​ with integers ppp and qqq, where q≠0q\ne0q=0.

Part 4 done

Quick check

One question on the part you just read

Easy

Identify the inductive hypothesis in a proof by induction.
Show answer and explanation

Answer: A · Worked explanation

The inductive hypothesis is the assumption that the statement holds for n=kn=kn=k. The check for the first value is the base case. Proving the statement for n=k+1n=k+1n=k+1 is the aim of the inductive step. The inductive hypothesis is the one fact the inductive step is allowed to use as given.
5

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 n2+n+41n^2+n+41n2+n+41 is prime for every positive integer nnn. It works for n=1n=1n=1, 2 and 3, and for many more values. But n=40n=40n=40 gives 1600+40+41=1681=4121600+40+41=1681=41^21600+40+41=1681=412, which is not prime. One failure is enough.

Common mistake

Checking many cases never proves a general claim. Only induction or a logical argument does.

Three methods compared

MethodUsed forMain idea
Inductiontruth for all integers from a start valuebase case, then step from kkk to k+1k+1k+1
Contradictionproving a claim by ruling out its oppositeassume the opposite, reach an impossibility
Counterexampleshowing a claim is falsefind one case where it fails
Method
Induction
Used for
truth for all integers from a start value
Main idea
base case, then step from kkk to k+1k+1k+1
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 nnn 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.

Note read

Check your recall[14 marks]

6 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 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 n=kn=kn=k gives truth for n=k+1n=k+1n=k+1.

    • 1 mark for stating that the base case holds
    • 1 mark for stating that truth for n=kn=kn=k implies truth for n=k+1n=k+1n=k+1
  2. 2.Identify[2 marks]

    Identify the inductive hypothesis when proving ∑r=1n(2r−1)=n2\sum_{r=1}^{n}(2r-1)=n^2∑r=1n​(2r−1)=n2 by induction.

    Show mark schemeHide mark scheme

    Model answer

    Assume the statement is true for n=kn=kn=k, that is ∑r=1k(2r−1)=k2\sum_{r=1}^{k}(2r-1)=k^2∑r=1k​(2r−1)=k2 for some positive integer kkk.

    • 1 mark for stating that the assumption is made for n=kn=kn=k
    • 1 mark for writing the statement as ∑r=1k(2r−1)=k2\sum_{r=1}^{k}(2r-1)=k^2∑r=1k​(2r−1)=k2
  3. 3.Explain[2 marks]

    Explain why checking the statement for the first five values of nnn does not prove it for all nnn.

    Show mark schemeHide mark scheme

    Model answer

    A finite number of checks cannot cover every positive integer. A counterexample may appear for a larger nnn, whereas induction covers every value through the inductive step.

    • 1 mark for stating that checking finitely many cases does not cover every nnn
    • 1 mark for stating that a later case could still fail, or that induction is needed to cover all nnn
  4. 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. 5.Write down[2 marks]

    Write down a counterexample to the claim that n2>nn^2>nn2>n for every positive integer nnn.

    Show mark schemeHide mark scheme

    Model answer

    Take n=1n=1n=1. Then n2=1n^2=1n2=1 and n=1n=1n=1, and 1>11>11>1 is false.

    • 1 mark for choosing n=1n=1n=1
    • 1 mark for showing that 12=11^2=112=1 is not greater than 1
  6. 6.Deduce[3 marks]

    Given that 7k−17^k-17k−1 is divisible by 6, deduce that 7k+1−17^{k+1}-17k+1−1 is divisible by 6.

    Show mark schemeHide mark scheme

    Model answer

    Write 7k−1=6m7^k-1=6m7k−1=6m. Then 7k+1−1=7(7k−1)+6=42m+6=6(7m+1)7^{k+1}-1=7\left(7^k-1\right)+6=42m+6=6(7m+1)7k+1−1=7(7k−1)+6=42m+6=6(7m+1), which is a multiple of 6.

    • 1 mark for writing 7k+1−1=7(7k−1)+67^{k+1}-1=7\left(7^k-1\right)+67k+1−1=7(7k−1)+6
    • 1 mark for substituting 7k−1=6m7^k-1=6m7k−1=6m to obtain 6(7m+1)6(7m+1)6(7m+1)
    • 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.

3.

Easy·State[1 mark]

State what a counterexample shows.
Show answer and explanation

Answer: A · Worked explanation

A single case that breaks a general claim is enough to show the claim is false. A case where the claim holds, or many such cases, never proves a general claim. Only a failing case counts, because the claim says every case works.
4.

Medium·Determine[1 mark]

Determine the correct first line of a proof by contradiction that there is no greatest even integer.
Show answer and explanation

Answer: A · Worked explanation

Contradiction starts by assuming the opposite of the claim. The opposite of ‘there is no greatest even integer’ is ‘some even integer NNN is the greatest’. Assuming the claim itself gives nothing to contradict. A good test is whether the first line says the opposite of what you want to prove.
5.

Medium·Deduce[1 mark]

In a proof by contradiction that 2\sqrt22​ is irrational, 2=pq\sqrt2=\frac{p}{q}2​=qp​ leads to p2=2q2p^2=2q^2p2=2q2. Deduce what this shows about ppp.
Show answer and explanation

Answer: A · Worked explanation

Since p2=2q2p^2=2q^2p2=2q2, the number p2p^2p2 is even, and the square of an odd number is odd, so ppp is even. That qqq is also even needs a further step after writing p=2mp=2mp=2m. Only p2p^2p2 is forced to be a multiple of 4, not ppp.
6.

Medium·Determine[2 marks]

Given that 7k−1=6m7^k-1=6m7k−1=6m, determine an expression for 7k+1−17^{k+1}-17k+1−1 in terms of mmm.
Show answer and explanation

Answer: A · Worked explanation

Write 7k+1−1=7(7k−1)+6=7(6m)+6=42m+6=6(7m+1)7^{k+1}-1=7\left(7^k-1\right)+6=7(6m)+6=42m+6=6(7m+1)7k+1−1=7(7k−1)+6=7(6m)+6=42m+6=6(7m+1). The value 42m42m42m drops the +6+6+6. The value 6(m+1)6(m+1)6(m+1) adds 6 to 6m6m6m instead of multiplying by 7 first. Check with k=1k=1k=1: 71−1=67^1-1=671−1=6 gives m=1m=1m=1, and 6(7+1)=48=72−16(7+1)=48=7^2-16(7+1)=48=72−1.
7.

Medium·Determine[2 marks]

Determine which value of nnn is a counterexample to the claim that 2n>n22^n>n^22n>n2 for every positive integer nnn.
Show answer and explanation

Answer: A · Worked explanation

For n=3n=3n=3, 23=82^3=823=8 and 32=93^2=932=9, so 8>98>98>9 is false. The other values satisfy the claim: 2>12>12>1 for n=1n=1n=1, 32>2532>2532>25 for n=5n=5n=5 and 64>3664>3664>36 for n=6n=6n=6. A value that satisfies the claim cannot disprove it. Testing small values in turn finds the failure quickly.
8.

Hard·Determine[2 marks]

Assume that ∑r=1kr2=k(k+1)(2k+1)6\sum_{r=1}^{k}r^2=\frac{k(k+1)(2k+1)}{6}∑r=1k​r2=6k(k+1)(2k+1)​. Determine the simplified expression for ∑r=1k+1r2\sum_{r=1}^{k+1}r^2∑r=1k+1​r2.
Show answer and explanation

Answer: A · Worked explanation

Add the next term: k(k+1)(2k+1)6+(k+1)2\frac{k(k+1)(2k+1)}{6}+(k+1)^26k(k+1)(2k+1)​+(k+1)2. Factor out (k+1)(k+1)(k+1) to get (k+1)(2k2+7k+6)6=(k+1)(k+2)(2k+3)6\frac{(k+1)\left(2k^2+7k+6\right)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}6(k+1)(2k2+7k+6)​=6(k+1)(k+2)(2k+3)​. Replacing kkk by k+1k+1k+1 in only some factors, as in (k+1)(k+2)(2k+1)(k+1)(k+2)(2k+1)(k+1)(k+2)(2k+1), is a common slip. Check with k=1k=1k=1: the sum of the first two squares is 5, and 2×3×56=5\frac{2\times3\times5}{6}=562×3×5​=5.
9.

Hard·Determine[2 marks]

A student proves a statement is true for n=1n=1n=1, and proves that truth for n=kn=kn=k implies truth for n=k+2n=k+2n=k+2. Determine the values of nnn for which the statement is proved.
Show answer and explanation

Answer: A · Worked explanation

Starting at 1 and moving in steps of 2 reaches 1, 3, 5 and so on, which are the odd integers. Even integers are never reached, so the statement is not proved for all positive integers. The step applies repeatedly, so it does not stop at n=3n=3n=3.
10.

Hard·Identify[2 marks]

A student claims that n2+n+41n^2+n+41n2+n+41 is prime for every positive integer nnn. Identify a value of nnn that disproves the claim.
Show answer and explanation

Answer: A · Worked explanation

For n=40n=40n=40, 1600+40+41=1681=4121600+40+41=1681=41^21600+40+41=1681=412, which is not prime, so this is a counterexample. The values n=1n=1n=1 and n=2n=2n=2 give 43 and 47, both prime, and n=39n=39n=39 gives 1601, also prime. Passing many tests does not prove the claim. Only one failing value is needed to disprove the claim.

Keep going

Next topic1.16 Systems of linear equationsPrevious topic1.14 Complex roots and De Moivre's theorem

More in Topic 1 · Number and algebra

  1. 1.8Infinite geometric seriesNotes · 10 questions
  2. 1.9The binomial theoremNotes · 10 questions
  3. 1.10Counting principlesNotes · 10 questions· HL only
  4. 1.11Partial fractionsNotes · 10 questions· HL only
  5. 1.12Complex numbersNotes · 10 questions· HL only
  6. 1.13Polar and Euler formNotes · 10 questions· HL only
  7. 1.14Complex roots and De Moivre's theoremNotes · 10 questions· HL only
  8. 1.15Proof by induction and contradictionNotes · 10 questions· HL only
  9. 1.16Systems of linear equationsNotes · 10 questions· HL only

All IB Mathematics: Analysis and Approaches topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/5 read

  1. 1Induction proves a statement for every positive integer
  2. 2The inductive step assumes the statement is true for some k
  3. 3Induction also proves divisibility and inequality statements
  4. 4Proof by contradiction assumes the opposite and finds an impossibility
  5. 5A single counterexample disproves a general claim
  6. Check your recall
  7. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe