Proving Divisibility Results with Strong Induction
You'll learn how to use strong induction to prove that certain expressions are always divisible by a fixed integer for all valid n.
The Core Idea
Some divisibility statements depend on multiple previous cases, not just the immediately preceding one. Strong induction is perfect here because it lets you assume the statement holds for all earlier values (not just n-1) when proving it for n.
Why Strong Induction Fits Divisibility
Divisibility proofs often require combining results from several earlier terms. For example, if you need to show that aₙ is divisible by d, you might express aₙ as a combination of aₙ₋₁ and aₙ₋₂. Strong induction gives you both facts simultaneously.
Structure of the Proof
- Base case(s): Verify divisibility for the smallest value(s) of n
- Inductive hypothesis: Assume the divisibility holds for all k where base ≤ k ≤ n (strong assumption)
- Inductive step: Prove it for n+1 using any/all previous cases you need
Example Pattern
Claim: For all n ≥ 1, the number 5^n - 1 is divisible by 4.
- Base: n=1: 5¹ - 1 = 4, which is divisible by 4 ✓
- Hypothesis: Assume 5^k - 1 is divisible by 4 for all k ≤ n
- Step: Consider 5^(n+1) - 1 = 5·5^n - 1 = 5(5^n - 1) + 5 - 1 = 5(5^n - 1) + 4
Since 5^n - 1 is divisible by 4 (by hypothesis) and 4 is divisible by 4, their sum is divisible by 4.
Key Takeaway: Strong induction is ideal for divisibility proofs involving recursive formulas or expressions that depend on multiple previous terms—your inductive hypothesis covers all earlier cases you might need to combine.