17  Mathematical Proof — Induction

18 Mathematical Proof — Induction

Week 8, Session 1. CSS 342.

18.1 Warmup

What is 1 + 2 + 3 + … + 100? Gauss’s schoolteacher allegedly gave him this problem to keep him busy. He answered in seconds: 5050. How?

Pair up: (1 + 100), (2 + 99), …, (50 + 51). Fifty pairs, each summing to 101. Total: 50 × 101 = 5050.

That trick generalizes: 1 + 2 + … + n = n(n+1)/2. This chapter is the proof.

18.2 Learning objectives

  1. Carry out a proof by weak induction, clearly labeling the base case, inductive hypothesis, and inductive step.
  2. Explain why induction is the formal analog of recursion.
  3. Prove the closed form for 1 + 2 + … + n = n(n+1)/2 by induction.
  4. Apply induction to verify that a simple algorithm is correct.
  5. Recognize when strong induction is needed vs. weak induction.

18.3 The structure

To prove a statement P(n) holds for all integers n ≥ 1:

  1. Base case: prove P(1).
  2. Inductive hypothesis: assume P(k) for some k ≥ 1.
  3. Inductive step: prove P(k+1), using the assumption from step 2.

Conclusion: P(n) holds for all n ≥ 1.

The metaphor is a row of dominoes. Step 1 knocks over the first one. Step 3 shows that any standing domino knocks over the next. Together, every domino falls.

Induction is the formal version of recursion. Recursion says “I assume the smaller case works, and I use it to handle the bigger case.” Induction says the same thing in proof form. If you can write a recursive function, you can write an inductive proof — the structure is identical.

18.4 Proof 1: the canonical sum

Claim: For all n ≥ 1, 1 + 2 + 3 + … + n = n(n+1)/2.

Base case (n=1): The left side is 1. The right side is 1 × 2 / 2 = 1. ✓

Inductive hypothesis: Assume 1 + 2 + … + k = k(k+1)/2.

Inductive step: Show 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2.

Starting from the left side: \[ 1 + 2 + \ldots + k + (k+1) \]

By the IH, the first k terms sum to k(k+1)/2: \[ = \frac{k(k+1)}{2} + (k+1) \]

Common factor (k+1): \[ = (k+1) \cdot \left( \frac{k}{2} + 1 \right) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2} \]

Which is the right side with k+1 substituted. ✓

By induction, the claim holds for all n ≥ 1. ∎

18.5 Proof 2: an inequality

Claim: For all n ≥ 1, 2ⁿ > n.

Base case (n=1): 2¹ = 2 > 1. ✓

Inductive hypothesis: Assume 2ᵏ > k.

Inductive step: Show 2^(k+1) > k+1.

\[ 2^{k+1} = 2 \cdot 2^k > 2k \quad \text{(by IH)} \]

For k ≥ 1, 2k ≥ k+1 (because k ≥ 1 implies k ≥ 1, so 2k = k+k ≥ k+1). Therefore 2^(k+1) > k+1. ∎

18.6 Proof 3: divisibility

Claim: For all n ≥ 0, 3 divides n³ − n.

Base case (n=0): 0³ − 0 = 0. 3 divides 0. ✓

IH: Assume 3 divides k³ − k. So k³ − k = 3m for some integer m.

Inductive step: Show 3 divides (k+1)³ − (k+1).

Expand: \[ (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = k^3 - k + 3k^2 + 3k \]

By IH, k³ − k = 3m. So \[ = 3m + 3(k^2 + k) = 3(m + k^2 + k) \]

A multiple of 3. ∎

18.7 Strong induction

Weak induction assumes P(k) and proves P(k+1). Strong induction assumes P(1), P(2), …, P(k) — all previous cases — and proves P(k+1). It is necessary when the inductive step needs more than just the immediately previous case.

Example: Fibonacci. Define F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).

Claim: F(n) < 2ⁿ for all n ≥ 0.

Base cases: F(0) = 0 < 1 = 2⁰. F(1) = 1 < 2 = 2¹. (Two base cases because the recursion uses two previous values.)

IH: Assume F(j) < 2ʲ for all j < k.

Step: F(k) = F(k-1) + F(k-2) < 2^(k-1) + 2^(k-2) = 2^(k-2)(2 + 1) = 3 · 2^(k-2) < 4 · 2^(k-2) = 2ᵏ. ∎

18.8 Loop invariants — induction in your code

A loop invariant is a statement that holds before each iteration. Proving correctness of a loop usually means:

  1. Initialization: invariant holds before the first iteration.
  2. Maintenance: if it holds before iteration k, it holds before iteration k+1.
  3. Termination: when the loop ends, the invariant implies the desired result.

That is induction on the iteration number.

Example: bubble sort. Invariant: “after pass i, the last i elements are in their final sorted positions.” Initialization: i=0, nothing to claim, holds. Maintenance: each pass swaps the largest remaining element to the end. Termination: after n−1 passes, all but the first are sorted, and the first is therefore correctly placed too.

That informal argument is a proof sketch. Real algorithm correctness proofs in CSS 343 will make this rigorous.

18.9 Try it

Prove by induction that for all n ≥ 1, 1 + 3 + 5 + … + (2n−1) = n².

Sketch: - Base: n=1: LHS = 1 = 1². ✓ - IH: 1 + 3 + … + (2k−1) = k². - Step: add (2k+1) to both sides: k² + 2k + 1 = (k+1)². ✓

18.10 Self-check

1. Which is the inductive hypothesis in a weak induction proof?
c. Weak IH: assume P(k); prove P(k+1). Strong IH would assume P(j) for all j ≤ k.
2. Why is induction the formal analog of recursion?
b. Base case = base case; recursive call = inductive hypothesis; combining = inductive step.

18.11 Challenges

  1. Prove by induction: ∑ from i=1 to n of i² = n(n+1)(2n+1)/6.
  2. Prove the merge sort recurrence T(n) = 2T(n/2) + cn yields T(n) = O(n log n) using strong induction.
  3. State and prove a loop invariant for insertion sort.

18.12 Where this fits

You can now formally argue that an algorithm works, not just time it. Next chapter we build a data structure we will prove things about: the linked list.

You are here Coming up
Weak and strong induction, loop invariants Chapter 16: linked lists