MATH VAULT

Proof by Induction: A Step-by-Step Guide for A-Level

Proof by Induction: A Step-by-Step Guide for A-Level

Proof by induction is a way of proving that a statement involving a whole number n is true for every n from a starting value upwards. You prove it for the first case, then prove that if it works for any one case it must work for the next. Together, those two facts cover infinitely many cases. On A-Level courses it sits mainly in Further Maths, and it is one of the most predictable, mark-rich proof questions you will meet.

This guide shows you the structure examiners reward, works through three complete examples (a sum, a divisibility result and a matrix power), and lists the slips that cost marks. If you can reproduce the layout from memory, most induction questions become a matter of algebra.

Mathvault
Build Confidence in A-Level Maths
Practise exam maths with past papers, step-by-step solutions, video walkthroughs and live Q&A sessions on MathVault.

Explore maths resources

TL;DR

  • Every induction proof has four parts: the base case, the assumption for n = k, the step to n = k + 1, and a closing conclusion sentence.
  • Induction confirms a formula you already have. It does not find the formula for you.
  • It is examined in A-Level Further Maths (sums of series, divisibility, matrix powers and more), not in standard A-Level Maths on every board.
  • Sums: add the (k + 1)th term. Divisibility: rewrite the k + 1 case so the k case appears. Matrices: multiply by the matrix once more.
  • Marks are lost for a missing base case, a missing conclusion, and for assuming what you are meant to prove.

Table of Contents

What proof by induction actually does

A formula such as 1 + 2 + … + n = n(n + 1)/2 looks like one statement, but it abbreviates infinitely many separate claims: one for n = 1, one for n = 2, and so on. Borovik and Gardiner’s exposition makes this point clearly: induction works by establishing the first claim and a reliable transition from each claim to the next. Once both are secured, the statement holds for every positive integer n.

A helpful picture is a row of dominoes. The base case knocks over the first domino. The inductive step shows that any falling domino knocks over the next one. You do not need to push all of them yourself.

Two limits are worth knowing early:

  • Induction checks, it does not discover. The Cambridge Further Maths textbook excerpt notes that the method is useful for proving a conjectured formula is correct but does not help you find what the formula is.
  • Some questions ask you to spot the pattern first. The same source points out that inductive proofs sometimes require you to conjecture a pattern yourself, for example by calculating the first few terms of a sequence, before you prove it formally.

Where proof by induction appears in A-Level courses

The answer depends on the course and the exam board, so check your own specification rather than relying on a classmate.

In practice, expect to meet induction in Further Maths Pure papers. The Cambridge excerpt describes Further Maths students as expected to use induction for results about matrices, divisibility, inequalities, sequences and series. If you are weighing up how to tackle those papers as a whole, our Further Maths paper strategy guide covers timing and question order.

The four-part structure examiners expect

The mathcentre guide to proof sets out three steps: the base case, the inductive hypothesis and the inductive step. In exam answers there is a fourth part that earns its own mark: the conclusion. Learn all four as a template.

  1. State the claim. Write P(n) clearly at the top, so you and the examiner know exactly what is being proved.
  2. Base case. Show the statement is true for the starting value, usually n = 1 (sometimes n = 0 or a later value). Work out both sides separately and show they agree.
  3. Inductive hypothesis. Write: assume the statement is true for n = k, where k is a positive integer. Then write out what that assumption says, in full.
  4. Inductive step. Write out the statement for n = k + 1, then use the hypothesis to show it holds.
  5. Conclusion. Write a sentence that pulls it together: the statement is true for n = 1, and if it is true for n = k then it is true for n = k + 1, so by mathematical induction it is true for all positive integers n.

That is five lines of layout, but the logic is the four ideas above. Notice that the conclusion mentions both pieces. Examiners look for it, and omitting it is one of the commonest ways to drop an easy mark.

A note on why the base case matters

It can feel like a formality, but it is not. As Joy Morris of the University of Lethbridge explains in her induction notes, induction only proves the conditional transition from one case to the next. Without a true starting case, you could prove obviously false statements.

Worked example 1: proving a sum formula

Prove that for all positive integers n, 1² + 2² + … + n² = n(n + 1)(2n + 1)/6.

For sums, the method from the Cambridge excerpt is to add the (k + 1)th term to the sum of the first k terms and use the hypothesis to simplify.

Base case (n = 1). Left-hand side: 1² = 1. Right-hand side: 1 × 2 × 3 / 6 = 1. The two sides agree, so the statement is true for n = 1.

Assumption. Assume the statement is true for n = k, so

1² + 2² + … + k² = k(k + 1)(2k + 1)/6.

Inductive step. Consider n = k + 1. The left-hand side is

1² + 2² + … + k² + (k + 1)²

= k(k + 1)(2k + 1)/6 + (k + 1)² (using the assumption)

= (k + 1)[k(2k + 1) + 6(k + 1)] / 6 (factorising out k + 1)

= (k + 1)(2k² + 7k + 6) / 6

= (k + 1)(k + 2)(2k + 3) / 6.

This is exactly the right-hand side formula with n replaced by k + 1, since (k + 1) + 1 = k + 2 and 2(k + 1) + 1 = 2k + 3.

Conclusion. The statement is true for n = 1, and if it is true for n = k then it is true for n = k + 1. By mathematical induction it is true for all positive integers n.

The key move is factorising the common (k + 1) early. Expanding everything instead usually works, but it is slower and easier to get wrong. Always keep the target in view: you know what the n = k + 1 version of the formula looks like, so aim your algebra at it.

Worked example 1: proving a sum formula

Worked example 2: proving divisibility

Prove that 7ⁿ − 1 is divisible by 6 for all positive integers n.

The approach, as set out in the LibreTexts section on divisibility proofs, is to write the k + 1 expression so that the k case appears alongside terms that are visibly divisible by the required number. The hypothesis then makes the whole expression divisible.

Base case (n = 1). 7¹ − 1 = 6, which is divisible by 6.

Assumption. Assume 7ᵏ − 1 is divisible by 6 for some positive integer k. Equivalently, 7ᵏ − 1 = 6m for some integer m.

Inductive step. Consider 7ᵏ⁺¹ − 1.

7ᵏ⁺¹ − 1 = 7 × 7ᵏ − 1

= 7(7ᵏ − 1) + 7 − 1

= 7(7ᵏ − 1) + 6

= 7 × 6m + 6 (using the assumption)

= 6(7m + 1).

Since 7m + 1 is an integer, 7ᵏ⁺¹ − 1 is divisible by 6.

Conclusion. True for n = 1, and if true for n = k then true for n = k + 1, so by mathematical induction 7ⁿ − 1 is divisible by 6 for all positive integers n.

Writing the assumption as an equation (7ᵏ − 1 = 6m) is a habit worth building. It lets you substitute cleanly and makes the final line obvious to a marker.

Worked example 3: powers of a matrix

Let M be the matrix with rows (1, 1) and (0, 1). Prove that Mⁿ has rows (1, n) and (0, 1) for all positive integers n.

This is the classic Further Maths matrix-power question, and it is the case where you must usually be told the pattern or find it yourself by working out M², M³ and so on.

Base case (n = 1). M¹ = M, which has rows (1, 1) and (0, 1). The formula gives rows (1, 1) and (0, 1). They match.

Assumption. Assume Mᵏ has rows (1, k) and (0, 1).

Inductive step. Mᵏ⁺¹ = Mᵏ × M. Multiplying the matrix with rows (1, k) and (0, 1) by the matrix with rows (1, 1) and (0, 1):

  • Top row: (1 × 1 + k × 0, 1 × 1 + k × 1) = (1, 1 + k)
  • Bottom row: (0 × 1 + 1 × 0, 0 × 1 + 1 × 1) = (0, 1)

So Mᵏ⁺¹ has rows (1, k + 1) and (0, 1), which is the formula with n = k + 1.

Conclusion. True for n = 1, and true for n = k implies true for n = k + 1, so by mathematical induction the result holds for all positive integers n.

Here the order of multiplication matters. Matrix multiplication is not commutative in general, so write Mᵏ⁺¹ = Mᵏ × M, and keep that order throughout.

Other question types: sequences and inequalities

Once the template is automatic, the remaining question types are variations.

  • Recurrence relations. You are given something like uₙ₊₁ = 3uₙ + 2 with u₁ = 1, and asked to prove a closed form. Your hypothesis is the closed form for uₖ. In the step, substitute it into the recurrence to produce the formula for uₖ₊₁.
  • Inequalities. Here you cannot rearrange to an equals sign. Start from the k + 1 side, use the hypothesis to replace part of it with something smaller (or larger), and then show the remaining expression is at least what you need. Be explicit about which direction each inequality points, and note where you use the condition on k, such as k ≥ 4.
  • Starting values other than 1. Some results only hold from n = 4 or n = 5 upwards. The base case is then that starting value, and the conclusion must say so: true for all integers n ≥ 4.

Mistakes that cost marks

Most lost marks come from presentation and logic rather than hard algebra.

  • Skipping or half-doing the base case. Evaluate both sides and state that they agree. Writing only the left-hand side gets you nowhere.
  • Assuming the thing you are proving. In the k + 1 step you must start from one side and reach the other. Writing the n = k + 1 equation and manipulating both sides until they look similar is a circular argument.
  • Blurring the two sides. Dobson and Slomson of the University of Leeds, in the mathcentre proof guide, stress distinguishing left-hand and right-hand sides clearly at each stage. Label them LHS and RHS if it helps.
  • Not writing out the hypothesis. Say exactly what you are assuming for n = k. Otherwise, you may later use it incorrectly, or the examiner cannot see where you used it.
  • Forgetting to say where the assumption is used. A short note such as using the assumption protects your method marks.
  • Leaving out the conclusion sentence. Include both the base case and the implication, and name the method: by mathematical induction.
  • Using k and n interchangeably. Your assumption is about k. Your final statement is about n. Mixing them makes the logic muddy.

Our perspective: treat induction as a template you rehearse

We see students approach induction as a clever trick that either clicks or does not. That is the wrong way round. Induction is one of the most formulaic proofs on the Further Maths course, which is exactly why it rewards practice. The thinking happens in a small number of places: choosing how to factorise in a sum, spotting how to split a power in a divisibility question, and setting out matrix multiplication in the right order.

Three recurring moves in induction proofs

Our advice has three parts. First, write the skeleton (claim, base case, hypothesis, step, conclusion) before you touch the algebra, so that the structure marks are already in the bank. Second, always write down the target, the n = k + 1 version of the statement, in the margin. It tells you what your algebra is heading towards. Third, after you have attempted a question, compare your layout line by line with a fully worked solution and a mark scheme, not just your final answer. Method and accuracy marks are awarded for the setup as much as for the arithmetic.

If you try a question cold first and only then check the solution, you will learn far more than by reading solutions in advance. Our note on written versus video solutions explains how to do that without falling into the trap of just recognising the working.

— Oloru

How to practise proof by induction

A sensible practice sequence looks like this:

  1. Copy one example of each type (sum, divisibility, matrix power) from your textbook, closing the book after each line you can reproduce.
  2. Attempt a fresh question of the same type with only your skeleton in front of you.
  3. Mark yourself against a mark scheme, tallying the structure marks (base case, hypothesis, conclusion) separately from the algebra marks.
  4. Repeat with mixed questions so that you have to decide which technique applies.
  5. Do timed exam questions once you can write a clean proof in around six to eight minutes.

We publish free A-Level past-paper questions with worked solutions, organised by topic and exam board, so you can find proof questions without hunting through whole papers. Start with our A-Level maths past-paper questions, and if you prefer a book to work from, the free Edexcel A-Level Maths and Further Maths textbooks include proof sections. Stuck on a line of algebra? Bring it to our weekly sessions: our guide to getting the most from A-Level maths live Q&A shows how to ask a question that gets a useful answer.

Mathvault

All our revision materials are free to use. If you want organised packs for offline use, or wish to support the site, you can do so, but you never need to pay to practise.

Frequently asked questions

Is proof by induction in A-Level Maths or only Further Maths?

It depends on the board, so read your specification. OCR states that induction is covered in Further Maths and is off specification in A-Level Maths. AQA and Pearson Edexcel list induction in their A-Level Further Maths content, so that is where you should expect it.

What are the steps in a proof by induction?

Prove the statement for a starting value, usually n = 1. Assume it is true for n = k. Use that assumption to prove it for n = k + 1. Finish with a conclusion sentence saying the statement is true for all positive integers n by mathematical induction.

How do I prove a divisibility result by induction?

Write the expression for n = k + 1 so that the n = k expression appears in it, plus terms you can see are multiples of the divisor. The hypothesis tells you the k part is divisible, so the whole expression is. The 7ⁿ − 1 example above shows it in full.

Can induction help me find a formula?

No. Induction only confirms a formula you already have. If a question asks you to find a pattern, work out the first few cases, conjecture the formula, and then prove it with induction.

Why do I lose marks even when my algebra is right?

The commonest reasons are a missing or incomplete base case, an unstated hypothesis and no conclusion sentence. Those are structure marks, separate from the algebra. Practise with a mark scheme so you can see exactly where each one is awarded.

Sources

Exam Sensei

Leave a Reply

Your email address will not be published. Required fields are marked *