Course contentsShow
← Mathematics
Lesson 2504 of 3,12150. Discrete Math — Logic and ProofFree lesson

Proving Divisibility Properties

Applying induction to show that expressions involving n are divisible by specific integers for all natural numbers.

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:

  1. Base case: Show that d divides f(1) (or whatever your starting value is).
  2. Inductive hypothesis: Assume d divides f(k) for some arbitrary natural number k.
  3. 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.