Proving Divisibility Properties
What You'll Learn
You'll learn how to use mathematical induction to prove that certain expressions involving n are always divisible by a specific integer for all natural numbers.
The Core Idea
When you have an expression like f(n) and you want to prove that some integer d divides f(n) for every natural number n, mathematical induction is your go-to tool. The strategy mirrors the standard inductive proof structure, but with a divisibility twist:
- Base case: Show that d divides f(1) (or whatever your starting value is).
- Inductive hypothesis: Assume d divides f(k) for some arbitrary natural number k.
- Inductive step: Prove that d divides f(k+1), using the hypothesis.
The key technique in the inductive step is algebraic manipulation: rewrite f(k+1) to expose f(k) as part of the expression. Since you've assumed d divides f(k), if the remaining terms are also divisible by d, you're done.
Example Strategy
Claim: n³ - n is divisible by 3 for all natural numbers n.
- Base: When n = 1, we get 1³ - 1 = 0, which is divisible by 3. ✓
- Hypothesis: Assume k³ - k is divisible by 3.
- Step: Consider (k+1)³ - (k+1). Expand it:
- (k+1)³ - (k+1) = k³ + 3k² + 3k + 1 - k - 1 = k³ - k + 3k² + 3k
- Notice: (k³ - k) is divisible by 3 (hypothesis), and 3k² + 3k = 3(k² + k) is clearly divisible by 3.
- Therefore, their sum is divisible by 3. ✓
Key Takeaway: To prove divisibility properties by induction, rewrite f(k+1) to isolate f(k) plus additional terms that are clearly divisible by your target integer.