Mathematical Induction

Jim Hefferon · GFDL + CC BY-SA 2.5 · Introduction to Proofs

Mathematical induction proves a statement for all natural numbers. Prove it for n=0 (the base case). Then prove: if it holds for n=k, it holds for n=k+1 (the inductive step). The two together guarantee it holds everywhere.

Example: sum of first n natural numbers

Claim: 1 + 2 + ... + n = n(n+1)/2 for all n at least 1. Base case: n=1 gives 1 = 1*2/2, which checks. Inductive step: assume it holds for k, then 1 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2. Done.

Scheme

; Induction: 1 + 2 + ... + n = n(n+1)/2

(define (sum-to n)
  (if (= n 0) 0
      (+ n (sum-to (- n 1)))))

(define (formula n) (/ (* n (+ n 1)) 2))

; Verify for many values of n
(define (verify n)
  (display "n=") (display n)
  (display "  sum=") (display (sum-to n))
  (display "  formula=") (display (formula n))
  (display "  match? ") (display (= (sum-to n) (formula n)))
  (newline))

(verify 1)
(verify 5)
(verify 10)
(verify 50)
(verify 100)

Example: 2^n > n for all n at least 0

Base case: 2^0 = 1 > 0. Inductive step: assume 2^k > k. Then 2^(k+1) = 2 * 2^k > 2k = k + k. For k at least 1, k at least 1, so k + k at least k + 1. So 2^(k+1) > k+1.

Scheme

; Induction: 2^n > n for all n >= 0.

(define (pow2 n)
  (if (= n 0) 1 (* 2 (pow2 (- n 1)))))

(define (check n)
  (display "2^") (display n) (display " = ") (display (pow2 n))
  (display " > ") (display n) (display "? ")
  (display (> (pow2 n) n))
  (newline))

(check 0)
(check 1)
(check 5)
(check 10)
(check 20)

Example: 3 divides n^3 - n

Base case: 0^3 - 0 = 0, and 3 divides 0. Inductive step: assume 3 divides k^3 - k. Then (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3(k^2 + k). The first term is divisible by 3 (inductive hypothesis), the second is clearly divisible by 3. Done.

Scheme

; Induction: 3 divides n^3 - n for all n >= 0.

(define (cube n) (* n n n))

(define (check n)
  (let ((val (- (cube n) n)))
    (display "n=") (display n)
    (display "  n^3-n=") (display val)
    (display "  div by 3? ") (display (= 0 (modulo val 3)))
    (newline)))

(check 0)
(check 1)
(check 2)
(check 5)
(check 10)
(check 17)

Strong induction

In strong induction, the inductive hypothesis assumes the statement holds for all values up to k, not just k. Useful when the step from k to k+1 depends on earlier values. Example: every integer at least 2 has a prime factorization. If n is prime, done. If composite, n = a*b where a, b are less than n and at least 2. By strong induction, each has a prime factorization. Combining them gives one for n.

Scheme

; Strong induction: every integer >= 2 has a prime factorization.

(define (factorize n)
  (define (go n d)
    (cond ((<= n 1) (list))
          ((= 0 (modulo n d)) (cons d (go (/ n d) d)))
          (else (go n (+ d 1)))))
  (go n 2))

(define (check n)
  (display n) (display " = ")
  (display (factorize n))
  (newline))

(check 2)
(check 12)
(check 30)
(check 97)
(check 360)

Neighbors

🔑 Logic Ch.9 — formal treatment of induction in predicate logic
🔢 Discrete Math Ch.2 — sequences and induction
🐱 Milewski Ch.19 — F-algebras: induction as initial algebra
🔑 Logic Ch.9 — mathematical induction in formal logic
🔢 Discrete Math Ch.2 — sequences and recurrences proved by induction
✏️ Induction.lean — machine-checked induction proofs
⚙ Algorithms Ch.2 — recursion uses the same inductive structure

← Contrapositive and Contradiction by june.kim Sets →