DWG NO. 9.4 — Lesson 4 of 6

Mathematical Induction

Unit 9: Sequences, Series, and Combinatorics · ~25 min

Objective Prove a formula or statement true for every positive integer n using the principle of mathematical induction.

Lesson 9.3 handed you closed-form formulas like Σi = n(n+1)/2 without proof. Checking it for n = 1, 2, 3 builds confidence, but no finite amount of checking proves it holds for every positive integer — there are infinitely many to check. Mathematical induction proves an infinite family of statements with a finite amount of work, by showing each one triggers the next.

The principle

Let P(n) be a statement about the positive integer n (for example, "1 + 2 + … + n = n(n+1)/2"). Induction has two parts:

Base case Show P(1) is true — the statement holds for the smallest case.
Inductive step Assume P(k) is true for some arbitrary positive integer k (the inductive hypothesis), and use that assumption to prove P(k+1) is also true.

Once both parts are established, P(1) being true forces P(2) true (by the inductive step with k=1), which forces P(3) true (k=2), and so on forever — like a row of dominoes where knocking over the first guarantees every domino after it falls too, because each one is set up to knock over the next.

Base case topples P(1); the inductive step guarantees each P(k) topples P(k+1)

Worked Example 1 · Proving a sum formula

ProblemProve 1 + 2 + 3 + … + n = n(n+1)/2 for every positive integer n.

1Base case (n=1): left side = 1. Right side = 1(2)/2 = 1. Equal, so P(1) holds.

2Inductive hypothesis: assume 1 + 2 + … + k = k(k+1)/2 is true for some k ≥ 1.

3Show P(k+1): add (k+1) to both sides of the hypothesis: 1+2+…+k+(k+1) = k(k+1)/2 + (k+1).

4Factor the right side: k(k+1)/2 + (k+1) = (k+1)[k/2 + 1] = (k+1)(k+2)/2.

5That's exactly the formula n(n+1)/2 with n = k+1, so P(k+1) holds.

Base case + inductive step both hold ⇒ true for all n ≥ 1

Worked Example 2 · Proving a divisibility statement

ProblemProve n³ − n is divisible by 3 for every positive integer n.

1Base case (n=1): 1³ − 1 = 0, and 0 is divisible by 3. P(1) holds.

2Inductive hypothesis: assume k³ − k = 3m for some integer m.

3Show P(k+1): (k+1)³ − (k+1) = k³+3k²+3k+1 − k − 1 = (k³ − k) + 3k² + 3k.

4Substitute the hypothesis: = 3m + 3k² + 3k = 3(m + k² + k), which is divisible by 3.

Base case + inductive step both hold ⇒ true for all n ≥ 1

Guided practice

1.State the base case and the inductive hypothesis you would use to prove 2 + 4 + 6 + … + 2n = n(n+1) for all n ≥ 1.
Show answer

Base case: n=1, check 2 = 1(2) ✓. Inductive hypothesis: assume 2+4+…+2k = k(k+1) is true for some k ≥ 1.
2.Prove by induction that 1 + 3 + 5 + … + (2n−1) = n² for all positive integers n.
Show answer

Base: n=1, 1 = 1² ✓. Assume 1+3+…+(2k−1) = k². Add (2k+1): k²+(2k+1) = (k+1)². This is the formula with n=k+1, so P(k+1) holds, completing the proof.
3.Verify the base case only (do not complete the full proof) for: \(3^{n}\) ≥ 2n + 1 for all n ≥ 1.
Show answer

n=1: \(3^{1}\) = 3, and 2(1)+1 = 3. 3 ≥ 3 is true, so the base case holds.
4.Prove by induction that \(4^{n}\) − 1 is divisible by 3 for all positive integers n.
Show answer

Base: n=1, 4−1=3, divisible by 3 ✓. Assume \(4^{k}\)−1 = 3m. Then \(4^{k+1}\)−1 = 4·\(4^{k}\)−1 = 4(\(4^{k}\)−1) + 3 = 4(3m) + 3 = 3(4m+1), divisible by 3. P(k+1) holds.
5.Use the closed-form formula from Lesson 9.3 to write the statement P(n) you would prove for \(\sum_{i=1}^{n}\) i² = n(n+1)(2n+1)/6, and check the base case.
Show answer

P(n): 1²+2²+…+n² = n(n+1)(2n+1)/6. Base case n=1: left side = 1, right side = 1(2)(3)/6 = 1. Equal, so P(1) holds.

← 9.3 Summation Notation and Series Properties Unit Overview 9.5 The Binomial Theorem →