Divisibility Proofs by Induction
What you'll learn: How to use mathematical induction to prove that expressions are always divisible by certain numbers.
The Core Idea
Divisibility proofs by induction combine two powerful concepts you've already learned: mathematical induction and divisibility properties. You prove that for all natural numbers n, some expression involving n is divisible by a fixed number k.
The structure follows the familiar induction pattern:
- Base Case: Show the expression is divisible by k when n equals your starting value (usually n=0 or n=1)
- Inductive Hypothesis: Assume the expression is divisible by k for some arbitrary value n=m
- Inductive Step: Prove it's divisible by k for n=m+1
Example: Proving n³ - n is Divisible by 3
Let's prove that n³ - n is always divisible by 3 for all n ≥ 1.
Base Case (n=1): 1³ - 1 = 0, and 0 is divisible by 3. ✓
Inductive Hypothesis: Assume m³ - m is divisible by 3 for some m ≥ 1. This means m³ - m = 3k for some integer k.
Inductive Step: We need to show (m+1)³ - (m+1) is divisible by 3.
Expand: (m+1)³ - (m+1) = m³ + 3m² + 3m + 1 - m - 1 = m³ - m + 3m² + 3m = (m³ - m) + 3(m² + m)
By our hypothesis, (m³ - m) = 3k, so: = 3k + 3(m² + m) = 3(k + m² + m)
This is clearly divisible by 3! The induction is complete.
Key Takeaway: Divisibility proofs by induction work by showing the base case is divisible, then cleverly rewriting the (n+1) expression to expose both the divisible inductive hypothesis term and additional multiples of the divisor.