Hard

Proving Divisibility Statements by Induction

Simple Explanation

To prove an expression f(n) is always divisible by a fixed number d, verify the base case directly, then assume f(k) = d·m for some integer m (the inductive hypothesis), and use algebra to rewrite f(k+1) so it is ALSO clearly d times some integer.

Why Do We Need It?

Divisibility properties come up constantly in number theory and cryptography, and induction is the standard way to prove such a property holds for every single positive integer, not just the ones checked by hand.

Formula

Divisibility Proofs by Induction

Assume f(k) = d·m for some integer m; show f(k+1) = d·(some integer)

To prove f(n) is always divisible by a fixed number d, verify the base case directly, then assume f(k) equals d times some integer, and algebraically show f(k+1) must also equal d times some integer.

d: — the fixed divisor being proved to always divide f(n)
m: — the (unknown but existing) integer such that f(k) = d·m, by the inductive hypothesis

When to use it: Whenever a formula or expression needs to be proved divisible by a fixed number for every positive integer n.

Worked Example

Prove a divisibility statement using induction

Prove that 3ⁿ − 1 is divisible by 2, for all positive integers n ≥ 1.

Why Does This Work?

Rewriting 3^(k+1) as 3·3ᵏ is the key algebraic move that lets the inductive hypothesis (a fact about 3ᵏ) actually get substituted in — from there, it is just algebra to show the result still has a factor of 2, exactly the pattern needed to complete the inductive step.

Real-Life Example

Verifying a cryptographic sequence property

A cryptography engineer needs to guarantee that a computed value at every step of an unbounded process is always divisible by a fixed number, a property the security of the scheme depends on.

A divisibility induction proof rigorously confirms this holds at every single step, not merely the first several checked by hand.

Practice

Verify the base case for "5ⁿ − 1 is divisible by 4" at n=1: what is 5¹ − 1?

Hard

Common mistake

Forgetting to explicitly rewrite 3^(k+1) in terms of 3ᵏ (using 3^(k+1) = 3·3ᵏ) before substituting the inductive hypothesis — without this rewriting step, the hypothesis cannot be applied at all.

Quick Review

Base case: verify f(1) is divisible by d directly.
Inductive hypothesis: assume f(k) = d·m for some integer m.
Rewrite f(k+1) in terms of f(k), substitute, then factor out d.