What happens if I can't prove the inductive step?

First, double-check your algebra. It's the most common source of error. Second, ensure you have correctly used the inductive hypothesis ($P(k)$). A proof of $P(k+1)$ that doesn't rely on $P(k)$ is not a proof by induction. If you're still stuck, reconsider your approach. For divisibility, is $f(k+1)-f(k)$ helpful, or maybe $f(k+1) - c \cdot f(k)$ for some constant $c$?

Can I work backwards from the $n=k+1$ case?

You must be very careful. It is not valid to assume the $n=k+1$ result is true and work backwards to the $n=k$ assumption. However, you can use the target expression for $n=k+1$ as a 'goal' on your scrap paper to guide the manipulation of your starting expression. Your final written proof must flow logically from the LHS to the RHS of the $P(k+1)$ statement.

Do I have to write the full concluding sentence every time?

Yes, absolutely. Examiners look for it. A statement like 'Since the statement is true for $n=1$ and if it's true for $n=k$ it is also true for $n=k+1$, it is true for all positive integers $n$ by the principle of mathematical induction' is essential for full marks. It shows you understand the logical principle you are using.

Is proof by induction only for positive integers?

No. The statement might be for all integers $n \ge n_0$, where $n_0$ could be any integer, such as 0, 2, or even -5. Your base case would then be to prove the statement for $n=n_0$, and your assumption would be for $k \ge n_0$.

Where can I learn Proof by induction for Cambridge 9231?

This free lesson on MarkScheme covers syllabus point 1.7 (Proof by induction) for Cambridge A-Level Further Mathematics. It includes visual revision, key points, and links to real past-paper questions with mark-scheme marking at markscheme.app/courses/9231/1-7-proof-by-induction.

Is Proof by induction (1.7) on 9231 free to study?

Yes. The Further Mathematics 9231 course on MarkScheme is 100% free — including premium visual lessons, exam tips, and past-paper marking. No paywall for Proof by induction.

Proof by induction 9231 — Free A-Level Further

Proof by induction

Welcome to proof by induction, one of the most powerful tools in a mathematician's arsenal. While it might seem complex at first, it's a highly structured and logical process. Think of it as a formal way of setting off a chain reaction. This topic is a cornerstone of pure mathematics and frequently appears on Paper 1, so mastering its structure is key to success.

BY THE END, YOU CAN…

1Understand the principle of mathematical induction and its logical structure.
2Apply proof by induction to statements involving series, divisibility, and matrices.
3Construct a clear, rigorous, and complete proof that meets exam standards.
4Identify and avoid common errors, such as a weak conclusion or failing to use the inductive hypothesis.

In simple terms

A friendly intro before the formal notes — no formulas yet.

The Domino Effect of Proofs

Proof by induction is a method to prove a statement for an infinite sequence of numbers. It works by first proving the statement for the very first number, and then proving that if it's true for any number, it must also be true for the next one.

THINK OF IT LIKE…

Imagine an infinitely long line of dominoes. To be certain they will all fall, you don't need to knock each one over individually. You only need to verify two things: 1) you can knock over the very first domino, and 2) the dominoes are spaced correctly so that if any single domino falls, it is guaranteed to knock over the next one in the line. If both conditions are met, the whole line will fall.

1
Base Case: Prove the statement is true for the first value, usually n=1. This is pushing the first domino.
2
Inductive Hypothesis: Assume the statement is true for an arbitrary integer n=k. This is assuming a random domino, the k-th one, falls.
3
Inductive Step: Use the assumption for n=k to prove the statement is also true for the next value, n=k+1. This shows that if the k-th domino falls, it knocks over the (k+1)-th one.
4
Conclusion: Conclude that by the principle of mathematical induction, the statement is true for all specified integers. This is the final declaration that the entire line of dominoes will fall.

Explore the concept

Use the live diagram and synced steps — play it or tap a step card to walk through.

Key formulas

Tap any symbol to reveal exactly what it means and its units.

$\mathbf{M}^k = \mathbf{F}(k)$

Tap a symbol — great for exam definitions

Full topic notes

Formal explanation with the rigour you need for the exam.

The Principle of Mathematical Induction

Mathematical induction is a method of proof used to establish that a given statement is true for a whole set of numbers, typically all positive integers. The proof relies on a 'domino effect'. If you can show the first domino falls, and that any falling domino knocks over the next, then you can conclude that all the dominoes will fall. In mathematical terms, this translates to a rigorous, four-step structure.

Base Case: Prove the statement holds for the first value, $n_0$ (e.g., $n=1$ ).
Inductive Hypothesis: Assume the statement is true for an arbitrary integer $n=k$ , where $k \ge n_0$ .
Inductive Step: Show that if the statement is true for $n=k$ , it must also be true for $n=k+1$ . This is the core of the proof.
Conclusion: A formal statement that combines the base case and inductive step to conclude the proof by the principle of mathematical induction.

Type 1: Proving Summation Formulae

A very common application of induction is to prove formulae for the sum of a series. For example, you might be asked to prove that the sum of the first $n$ square numbers, $\sum_{r=1}^{n} r^2$ , is equal to a specific formula in terms of $n$ . The key to the inductive step is to separate the $(k+1)$ -th term from the sum and then use your assumption for the sum up to $k$ .

Type 2: Proving Divisibility

Induction is also used to prove that an expression is divisible by a certain integer for all values of $n$ . The key here is in the inductive step. After assuming $f(k)$ is divisible by $d$ , you must analyse $f(k+1)$ . A common and effective strategy is to consider the difference $f(k+1) - f(k)$ and show that this difference is also divisible by $d$ . Since $f(k)$ is assumed to be divisible by $d$ , it follows that $f(k+1)$ must also be.

Type 3: Proving Statements about Matrices

The principle of induction extends to statements involving matrices, most commonly for proving a formula for the $n$ -th power of a matrix. The structure of the proof remains identical. The base case involves checking for $n=1$ . The inductive step involves assuming the formula for $\mathbf{M}^k$ and using it to prove the formula for $\mathbf{M}^{k+1}$ by considering the product $\mathbf{M}^{k+1} = \mathbf{M}^k \mathbf{M}$ .

Inductive Step for Matrices:

Assume $\mathbf{M}^k = \mathbf{F}(k)$ for some matrix formula $\mathbf{F}(k)$ .
Consider $\mathbf{M}^{k+1} = \mathbf{M}^k \mathbf{M}$ .
Substitute the assumption: $\mathbf{M}^{k+1} = \mathbf{F}(k) \mathbf{M}$ .
Perform the matrix multiplication and algebraic manipulation to show that $\mathbf{F}(k) \mathbf{M} = \mathbf{F}(k+1)$ .

Worked examples

See the formulas applied — reveal one step at a time, like the exam.

EXAMPLE 1

Use the method of mathematical induction to prove that for all positive integers $n$ ,

$\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)$

1
Let $P(n)$ be the statement $\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)$ .

EXAMPLE 2

Prove by induction that $f(n) = 7^n - 1$ is divisible by 6 for all integers $n \ge 1$ .

1
Let $P(n)$ be the statement ' $7^n - 1$ is divisible by 6'.

How it all connects

The big idea sits in the middle — tap a linked idea to explore the link.

MAIN IDEAProof by induction

Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.

Glossary

Try to recall each definition before you reveal it.

Quick check

Answer in your head first — then tap to check. No pressure.

Revision flashcards

Flip the card. Test yourself before the exam.

QUESTION · 1 / 10

What is the principle of mathematical induction?

TAP OR SPACE TO FLIP

ANSWER

A method to prove a statement $P(n)$ is true for all integers $n \ge n_0$ by showing $P(n_0)$ is true (base case) and that for any $k \ge n_0$ , if $P(k)$ is true, then $P(k+1)$ is also true (inductive step).

TAP OR SPACE TO FLIP BACK

1 / 10 · ← → space

Key takeaways

Review these before you close the topic — retrieval beats re-reading.

✓
Base Case: Prove the statement holds for the first value, $n_0$ (e.g., $n=1$ ).
✓
Inductive Hypothesis: Assume the statement is true for an arbitrary integer $n=k$ , where $k \ge n_0$ .
✓
Inductive Step: Show that if the statement is true for $n=k$ , it must also be true for $n=k+1$ . This is the core of the proof.
✓
Conclusion: A formal statement that combines the base case and inductive step to conclude the proof by the principle of mathematical induction.

Practice — then mark it

The whole point: a real Cambridge question, marked mark-by-mark.

Real past paper[0]

Proof by Induction

Do it on paper → mark itMARKED MARK-BY-MARK · B1 / M1 / A1 · OFFICIAL SCHEME

Extra simulations & links

PhET, GeoGebra and other curated tools — open in a new tab.

Frequently asked

✓

Checkpoint

One marked question is worth ten re-reads — close the loop before you move on.

Checkpoint

Reading it isn’t knowing it — prove it.

Before you move on: do Proof by Induction on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.

Attempt & get marked →Takes about a minute · you’ll land back on this lesson

← PREVIOUS1.6 Vectors NEXT →2.1 Hyperbolic functions

Proof by induction

BY THE END, YOU CAN…

1Understand the principle of mathematical induction and its logical structure.
2Apply proof by induction to statements involving series, divisibility, and matrices.
3Construct a clear, rigorous, and complete proof that meets exam standards.
4Identify and avoid common errors, such as a weak conclusion or failing to use the inductive hypothesis.

In simple terms

A friendly intro before the formal notes — no formulas yet.

The Domino Effect of Proofs

THINK OF IT LIKE…

1
Base Case: Prove the statement is true for the first value, usually n=1. This is pushing the first domino.
2
Inductive Hypothesis: Assume the statement is true for an arbitrary integer n=k. This is assuming a random domino, the k-th one, falls.
3
Inductive Step: Use the assumption for n=k to prove the statement is also true for the next value, n=k+1. This shows that if the k-th domino falls, it knocks over the (k+1)-th one.
4
Conclusion: Conclude that by the principle of mathematical induction, the statement is true for all specified integers. This is the final declaration that the entire line of dominoes will fall.

Explore the concept

Use the live diagram and synced steps — play it or tap a step card to walk through.

Key formulas

Tap any symbol to reveal exactly what it means and its units.

$\mathbf{M}^k = \mathbf{F}(k)$

Tap a symbol — great for exam definitions

Full topic notes

Formal explanation with the rigour you need for the exam.

The Principle of Mathematical Induction

Base Case: Prove the statement holds for the first value, $n_0$ (e.g., $n=1$ ).
Inductive Hypothesis: Assume the statement is true for an arbitrary integer $n=k$ , where $k \ge n_0$ .
Inductive Step: Show that if the statement is true for $n=k$ , it must also be true for $n=k+1$ . This is the core of the proof.
Conclusion: A formal statement that combines the base case and inductive step to conclude the proof by the principle of mathematical induction.

Type 1: Proving Summation Formulae

Type 2: Proving Divisibility

Type 3: Proving Statements about Matrices

Inductive Step for Matrices:

Assume $\mathbf{M}^k = \mathbf{F}(k)$ for some matrix formula $\mathbf{F}(k)$ .
Consider $\mathbf{M}^{k+1} = \mathbf{M}^k \mathbf{M}$ .
Substitute the assumption: $\mathbf{M}^{k+1} = \mathbf{F}(k) \mathbf{M}$ .
Perform the matrix multiplication and algebraic manipulation to show that $\mathbf{F}(k) \mathbf{M} = \mathbf{F}(k+1)$ .

Worked examples

See the formulas applied — reveal one step at a time, like the exam.

EXAMPLE 1

Use the method of mathematical induction to prove that for all positive integers $n$ ,

$\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)$

1
Let $P(n)$ be the statement $\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)$ .

EXAMPLE 2

Prove by induction that $f(n) = 7^n - 1$ is divisible by 6 for all integers $n \ge 1$ .

1
Let $P(n)$ be the statement ' $7^n - 1$ is divisible by 6'.

How it all connects

The big idea sits in the middle — tap a linked idea to explore the link.

MAIN IDEAProof by induction

Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.

Glossary

Try to recall each definition before you reveal it.

Quick check

Answer in your head first — then tap to check. No pressure.

Revision flashcards

Flip the card. Test yourself before the exam.

QUESTION · 1 / 10

What is the principle of mathematical induction?

TAP OR SPACE TO FLIP

ANSWER

TAP OR SPACE TO FLIP BACK

1 / 10 · ← → space

Key takeaways

Review these before you close the topic — retrieval beats re-reading.

✓
Base Case: Prove the statement holds for the first value, $n_0$ (e.g., $n=1$ ).
✓
Inductive Hypothesis: Assume the statement is true for an arbitrary integer $n=k$ , where $k \ge n_0$ .
✓
Inductive Step: Show that if the statement is true for $n=k$ , it must also be true for $n=k+1$ . This is the core of the proof.
✓
Conclusion: A formal statement that combines the base case and inductive step to conclude the proof by the principle of mathematical induction.

Practice — then mark it

The whole point: a real Cambridge question, marked mark-by-mark.

Real past paper[0]

Proof by Induction

Do it on paper → mark itMARKED MARK-BY-MARK · B1 / M1 / A1 · OFFICIAL SCHEME

Extra simulations & links

PhET, GeoGebra and other curated tools — open in a new tab.

Frequently asked

✓

Checkpoint

One marked question is worth ten re-reads — close the loop before you move on.

Checkpoint

Reading it isn’t knowing it — prove it.

Before you move on: do Proof by Induction on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.

Attempt & get marked →Takes about a minute · you’ll land back on this lesson

← PREVIOUS1.6 Vectors NEXT →2.1 Hyperbolic functions

Revise Proof by induction for Cambridge 9231 (1.7)

In simple terms

Explore the concept

Key formulas

Full topic notes

The Principle of Mathematical Induction

Type 1: Proving Summation Formulae

Type 2: Proving Divisibility

Type 3: Proving Statements about Matrices

Worked examples

How it all connects

Glossary

Quick check

Revision flashcards

Key takeaways

Practice — then mark it

Proof by Induction

Extra simulations & links

Frequently asked

Checkpoint

Reading it isn’t knowing it — prove it.

In simple terms

Explore the concept

Key formulas

Full topic notes

The Principle of Mathematical Induction

Type 1: Proving Summation Formulae

Type 2: Proving Divisibility

Type 3: Proving Statements about Matrices

Worked examples

How it all connects

Glossary

Quick check

Revision flashcards

Key takeaways

Practice — then mark it

Proof by Induction

Extra simulations & links

Frequently asked

Checkpoint

Reading it isn’t knowing it — prove it.

Discuss Proof by induction