Skip to main content
MathidiaMathematics Academy
Proof by induction
Lesson 16 of 75
Introduction

Induction structure

Objective. Write base, hypothesis, step and conclusion rigorously.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Proof by induction establishes a statement P(n) is true for all integers n from a starting value, by proving two things: a base case showing P(n₀) is true, and an inductive step showing that if P(k) is true for some k, then P(k+1) must also be true. The conclusion then states that, since the base case holds and truth passes from each case to the next, P(n) holds for all n ≥ n₀ by the principle of mathematical induction. Each stage must be written explicitly: stating the assumption clearly, performing the algebra, and reaching the required form for P(k+1).

Worked example

State the four distinct parts required in the structure of a proof by induction that a statement P(n) holds for all positive integers n.

?
Illustrated card showing ?
  1. 1First, prove the base case, typically P(1), directly by substitution
  2. 2Second, state the inductive hypothesis: assume P(k) is true for some integer k ≥ 1
  3. 3Third, use this assumption to prove P(k+1) is also true
  4. 4Fourth, write a conclusion stating that by induction, P(n) holds for all positive integers n

Answer: Base case, assumption, inductive step, conclusion

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students write the inductive step but never state the assumption 'Assume P(k) is true', or omit the final concluding sentence linking base case and step. Always write all four parts: base case, assumption, step, and conclusion.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard