Mathematical Induction

Craig DeLancey · A Concise Introduction to Logic, Ch. 9 · CC BY-SA 4.0

Mathematical induction proves a property holds for all natural numbers. Prove the base case (n = 0). Then prove that if it holds for n, it holds for n + 1. The chain of implications covers every number.

Weak induction

To prove ∀n P(n): (1) prove P(0) (base case), (2) prove P(k) → P(k+1) for arbitrary k (inductive step). The assumption P(k) is the inductive hypothesis.

Scheme

; Prove: sum of 1..n = n*(n+1)/2

; Base case: sum of 1..0 = 0 = 0*1/2
(display "Base case (n=0): ")
(display (= 0 (/ (* 0 1) 2))) (newline)

; Inductive step: assume sum(1..k) = k*(k+1)/2
;                 prove  sum(1..k+1) = (k+1)*(k+2)/2
; sum(1..k+1) = sum(1..k) + (k+1)
;             = k*(k+1)/2 + (k+1)     [by IH]
;             = (k+1)*(k/2 + 1)
;             = (k+1)*(k+2)/2         QED

; Verify for several values
(define (sum-formula n) (/ (* n (+ n 1)) 2))
(define (sum-actual n)
  (let loop ((i 1) (s 0))
    (if (> i n) s (loop (+ i 1) (+ s i)))))

(define (check n)
  (display "n=") (display n)
  (display ": formula=") (display (sum-formula n))
  (display " actual=") (display (sum-actual n))
  (display " match=") (display (= (sum-formula n) (sum-actual n)))
  (newline))

(check 0) (check 1) (check 5) (check 10) (check 100)

Strong induction

In strong induction, the inductive hypothesis assumes P(j) for ALL j ≤ k, not just P(k). This is equivalent to weak induction but sometimes easier to use. Useful when the inductive step needs cases smaller than k-1.

Scheme

; Strong induction example: every integer >= 2 has a prime factor
; Base: 2 is prime, so it has a prime factor (itself).
; Strong step: assume every j with 2 <= j <= k has a prime factor.
;   Case 1: k+1 is prime -> done.
;   Case 2: k+1 = a*b where 2 <= a,b <= k.
;     By IH, a has a prime factor p. p divides a, a divides k+1,
;     so p divides k+1.

(define (prime? n)
  (if (< n 2) #f
    (let loop ((d 2))
      (cond ((> (* d d) n) #t)
            ((= 0 (modulo n d)) #f)
            (else (loop (+ d 1)))))))

(define (smallest-prime-factor n)
  (let loop ((d 2))
    (cond ((> (* d d) n) n)
          ((= 0 (modulo n d)) d)
          (else (loop (+ d 1))))))

; Verify for 2..20
(let loop ((n 2))
  (if (> n 20) (display "All verified!")
    (begin
      (display "n=") (display n)
      (display " smallest prime factor=")
      (display (smallest-prime-factor n))
      (newline)
      (loop (+ n 1)))))

Structural induction

Structural induction generalizes mathematical induction to recursively defined structures (lists, trees, formulas). Base case: the simplest structures. Inductive step: if the property holds for the substructures, it holds for the whole structure.

Scheme

; Structural induction on lists:
; Prove: length(append(xs, ys)) = length(xs) + length(ys)

; Base case: xs = empty list
; length(append((), ys)) = length(ys) = 0 + length(ys). Done.

; Inductive step: assume it holds for xs.
; append(cons(x, xs), ys) = cons(x, append(xs, ys))
; length = 1 + length(append(xs, ys))
;        = 1 + length(xs) + length(ys)    [by IH]
;        = length(cons(x, xs)) + length(ys). Done.

; Verify:
(define (my-append xs ys)
  (if (null? xs) ys
    (cons (car xs) (my-append (cdr xs) ys))))

(define xs (list 1 2 3))
(define ys (list 4 5))

(display "length(append(xs,ys)) = ")
(display (length (my-append xs ys))) (newline)
(display "length(xs) + length(ys) = ")
(display (+ (length xs) (length ys))) (newline)
(display "Equal: ")
(display (= (length (my-append xs ys))
            (+ (length xs) (length ys))))

Well-ordering principle

Every non-empty set of natural numbers has a least element. This is equivalent to the principle of mathematical induction. If P fails for some n, it fails for a smallest n, and that contradicts the inductive step.

Scheme

; Well-ordering: every non-empty set of naturals has a minimum
; Equivalent to induction

; If we have a set S of naturals where the property FAILS,
; well-ordering says S has a minimum element m.
; But induction says: P(0) is true, and P(k)->P(k+1).
; So P can't fail at m, contradiction. S must be empty.

(define (well-ordered? s)
  (if (null? s) #t  ; vacuously true
    (let ((minimum (apply min s)))
      (display "Minimum of ") (display s)
      (display " is ") (display minimum) (newline)
      #t)))

(well-ordered? (list 5 3 8 1 9))
(well-ordered? (list 100 42 7))
(display "Every non-empty set of naturals has a least element.")

Neighbors

🔢 Levin Ch.2 — sequences and induction in discrete math
🐱 Milewski Ch.19 — F-algebras and catamorphisms (structural recursion as a functor)

← Identity and Functions by june.kim Soundness and Completeness →