Skip to main content
MathidiaMathematics Academy
Proof by induction
Lesson 20 of 75
Review

Strong induction

Objective. Use all preceding cases when one case is insufficient.

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

Learn: the key idea

Strong induction proves P(n) for all n by assuming P(m) holds for every integer m with n₀ ≤ m ≤ k, not just the single case P(k), before proving P(k+1). This is necessary when the step from k to k+1 relies on an earlier case further back than just k, such as proving facts about sequences defined by more than one previous term. For example, proving every integer greater than 1 has a prime factorisation uses strong induction, since a composite k+1 might split into two smaller factors, neither of which is simply k.

Worked example

A sequence satisfies u₁=1, u₂=3 and u_n = u_(n−1) + 2u_(n−2) for n ≥ 3. Use strong induction to prove u_n < 3ⁿ for all n ≥ 1, using the inductive step for n=k+1 ≥ 3.

A sequence satisfies u₁=1
Illustrated card showing A sequence satisfies u₁=1
  1. 1Base cases: u₁=1<3¹=3 and u₂=3<3²=9, both true
  2. 2Assume u_m < 3^m for all m with 1 ≤ m ≤ k, where k ≥ 2
  3. 3Then u_(k+1) = u_k + 2u_(k−1) < 3^k + 2×3^(k−1) = 3^(k−1)(3+2) = 5×3^(k−1)
  4. 4Since 5×3^(k−1) < 3×3^k = 3^(k+1) (as 5 < 9), u_(k+1) < 3^(k+1), completing the strong induction

Answer: Proved: u_n < 3ⁿ for all n ≥ 1 by strong induction

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 use strong induction's assumption but only actually use P(k) in the step, meaning ordinary induction would have sufficed, or conversely only assume P(k) when the proof genuinely needs an earlier term. Check exactly which previous cases the step requires.

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