Mathematical Induction

Mathematical induction proves that a statement P(n) is true for every integer n ≥ n₀. Think of an infinite line of dominoes:

1. Base case: prove P(n₀) — the first domino falls.
2. Inductive step: prove that if P(k) is true (the inductive hypothesis), then P(k + 1) is true — each domino knocks over the next.

Together they prove P(n) for all n ≥ n₀.

#Example 1: sum of the first n integers

Claim. 1 + 2 + … + n = n(n + 1)/2 for all n ≥ 1.

Base case (n = 1): left side 1, right side 1·2/2 = 1. ✓

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

1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2,

which is the formula for n = k + 1. ∎

#Example 2: divisibility

Claim. 3 divides n³ − n for all n ≥ 0.

Base: n = 0 gives 0, divisible by 3. ✓

Step: assume 3 | k³ − k. Then (k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k). Both parts are divisible by 3. ∎

#Example 3: an inequality

Claim. 2ⁿ > n² for all n ≥ 5.

Base: 2⁵ = 32 > 25. ✓

Step: assume 2ᵏ > k² with k ≥ 5. Then 2ᵏ⁺¹ = 2·2ᵏ > 2k² = k² + k² > k² + 2k + 1 = (k + 1)², because k² > 2k + 1 when k ≥ 3. ∎

(The base case matters: the claim is false for n = 2, 3, 4.)

#Checking a formula is not proving it

Code can test a formula for many n — useful for catching a wrong formula before you try to prove it:

def check(name, lhs, rhs, upto=50):
    bad = [n for n in range(1, upto + 1) if lhs(n) != rhs(n)]
    print(f"{name}: {'holds' if not bad else 'FAILS at n = ' + str(bad[0])} for n = 1..{upto}")

check("sum of first n odd numbers = n^2", lambda n: sum(2 * i - 1 for i in range(1, n + 1)), lambda n: n * n)
check("sum of squares = n(n+1)(2n+1)/6", lambda n: sum(i * i for i in range(1, n + 1)), lambda n: n * (n + 1) * (2 * n + 1) // 6)
check("sum of cubes = (n(n+1)/2)^2", lambda n: sum(i ** 3 for i in range(1, n + 1)), lambda n: (n * (n + 1) // 2) ** 2)
check("2^n > n^2", lambda n: 2 ** n > n * n, lambda n: True)

sum of first n odd numbers = n^2: holds for n = 1..50
sum of squares = n(n+1)(2n+1)/6: holds for n = 1..50
sum of cubes = (n(n+1)/2)^2: holds for n = 1..50
2^n > n^2: FAILS at n = 2 for n = 1..50

The last check fails at n = 2 — which is why that claim starts at n = 5.

#Strong induction

In strong induction the inductive step may assume P(n₀), P(n₀ + 1), …, P(k) — all earlier cases — to prove P(k + 1). Use it when the next case depends on cases further back.

Claim. Every integer n ≥ 2 is a product of primes. Proof. Base: 2 is prime. Step: consider k + 1. If it is prime, done. Otherwise k + 1 = a·b with 2 ≤ a, b ≤ k; by the hypothesis both a and b are products of primes, so k + 1 is too. ∎

Claim. Every postage of 12 or more rupees can be made from 4- and 5-rupee stamps. Proof. Base cases 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5. Step: for k + 1 ≥ 16, take the solution for k − 3 (true by hypothesis) and add one 4-rupee stamp. ∎

#Induction and computer science

• Recursion is induction in code: the base case of a recursive function is the base case of the proof, and the recursive call relies on the "inductive hypothesis" that smaller inputs are handled correctly.
• Loop invariants (correctness proofs) are induction on the number of iterations.
• Structural induction proves properties of trees and lists: true for the empty structure, and preserved when building larger ones.