Induction for divisibility

Objective. Prove integer divisibility statements.

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

Learn: the key idea

Induction for divisibility proves that an expression f(n) is divisible by a fixed integer m for all positive integers n, by showing f(n₀) is divisible by m, and that f(k+1) − f(k) (or a similar combination) is also divisible by m whenever f(k) is. This allows f(k+1) to be written as a multiple of f(k) plus a term already known to be a multiple of m, making f(k+1) a multiple of m too. For example, proving 3 divides 4ⁿ−1 uses 4^(k+1)−1 = 4(4^k−1)+3, where both terms are multiples of 3.

Worked example

Prove by induction that 5ⁿ − 1 is divisible by 4 for all positive integers n.

1 $Base case n=1: 5¹-1 = 4, which is divisible by 4$
2 $Assume 5^k - 1 = 4m for some integer m$
3 $Consider 5^(k+1) - 1 = 5\times5^k - 1 = 5(4m+1) - 1 = 20m + 5 - 1 = 20m + 4 = 4(5m+1)$
4 $This is a multiple of 4, so by induction 5ⁿ-1 is divisible by 4 for all positive integers n$

Answer: Proved: 5ⁿ − 1 is divisible by 4 for all n ≥ 1

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 check only the base case and assume the pattern continues, without the inductive step linking f(k) and f(k+1) algebraically. Divisibility must be proved for every step, not inferred from a few numerical examples.

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