Course contentsShow
← Computer Science
Lesson 91 of 2,8722. Discrete Mathematics for CSFree lesson

Divisibility Proofs by Induction

Using induction to prove divisibility statements, such as proving n³-n is always divisible by 3.

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:

  1. Base Case: Show the expression is divisible by k when n equals your starting value (usually n=0 or n=1)
  2. Inductive Hypothesis: Assume the expression is divisible by k for some arbitrary value n=m
  3. 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.