Lecture notes for Algorithm Design

Lecture Notes for Algorithm Design

Mathematical Induction, 28 October 1999

These are provisional lecture notes, expect changes.

a simple problem: show sum(i = 1 to n, i) = n(n + 1)/2
simple induction
1. if something is true for n, and also is true for n + 1, then it is true for all j >= n
2. the inductive hypothesis H(n) - n the parameter of the induction
3. the base case - show H(i) holds
4. the inductive step - assume H(j) is true for some j >= i and consider H(j + 1)
5. example
  1. show for all natural numbers x and n, xⁿ - 1 is divisible by x - 1
  2. hypothesis - H(n) = x - 1 div xⁿ - 1 for n = 0
  3. the inductive step - assume H(j) holds for some j >= 0 and consider H(j + 1)
6. can also assume H(j - 1) and show H(j), but be careful how you specify j.
7. another example
  1. two-coloring regions formed by n planar lines
  2. hypothesis - H(n) = the regions formed by n lines can be two colored
  3. base - H(1) is true
  4. induction - assume H(j) true for j >= 1 and consider H(j + 1)
what j things to induct over?
1. an example
  1. show sum(i = 1 to n, 2^-n) < 1
  2. hyp - H(n) = sum(i = 1 to n, 2^-n) < 1
  3. bas - H(1) = sum(i = 1 to 1, 2^-n) = 1/2 < 1
  4. ind - assume H(j) true for j >= 1 and consider H(j + 1), from the right
2. another example
  1. how many regions do n planer lines form
  2. subsidiary problem - how many regions does the nth line form
  3. hyp - H(n) = the nth line adds n regions
  4. bas - H(1), H(2), H(3) true by inspection
  5. ind - let H(j) be true for some j >= 1 and consider H(j + 1)
double induction, repeated induction
1. Euler's formula V + F = E + 2 - notice that V + F = E + 2 implies that V + (F - 1) = (E - 1) + 2, and that removing an edge can actually remove a face.
2. hyp - H(n) = V + n = E + 2
3. bas = H(1) = (V + 1 = E + 2) = (V = E + 1)
  1. a one-faced, connected, planar graph is a tree
  2. hyp - H'(n) = an n-node tree has n - 1 edges
  3. bas = H'(1) = a 1-node tree has 1 - 1 = 0 edges
  4. ind = let H'(j be true for some j >= 1 and consider H'(j + 1)
  5. notice that reducing V = E + 1 by one on each side reduces the problem to the assumed hypothesis, if such a reduction makes sense. Fortunately, the graph is a tree and the reduction does make sense (that is, a tree always has at least one vertex connected to the tree by one edge)
4. ind - let H(j) be true for some j >= 1 and consider H(j + 1)
strong induction
1. rather than assume H(j) true for some h >= 1, assume H(1), H(2), . . ., H(j) true.
2. example
  1. independent set, induced subgraph
  2. hyp - H(n) = any n-node directed graph has a two-path-connected independent set
  3. bas - H(1), H(2), H(3) hold
  4. ind - assume H(j) holds for j >= 1 and consider H(j + 1)
    1. extract a vertex and all its neighbors - unfortunately, the resulting graph may not have j vertices
    2. strengthen the hypothesis to assume that all of H(1), H(2), . . ., and H(j) are true
    3. hyp - H(n) = any graph with up to n nodes has a two-path-connected independent set
3. another example
  1. disjoint paths between odd-degree vertices
  2. hyp - H(n) = pairs of odd-degree vertices in an n-edge connected, undirected graph can be connected by disjoint paths
  3. bas - H(1) is true
  4. ind - assume H(j) holds for j >= 1 and consider H(j + 1)
    1. if there are two odd vertices, there is a path between them; remove it and consider the remaining graph - but it may not be a connected graph, and we can't use the inductive hypothesis
    2. strengthen the hypothesis by eliminating the connected part
    3. now consider a pair of odd-degree vertices in the same component
loop invariants and program proofs
1. the loop invariant method
  1. each loop gets an invariant (the hypothesis)
  2. show the invariant is true before the loop executes (the basis step)
  3. show the invariant is true after each iteration of the loop (the inductive step)
  4. at loop termination, use the invariant and the negated guard to prove the main theorem
2. example
  1. convert n to binary in array b
```
t <- n
k <- 0
do t > 0
  k <- k + 1
  b[k] <- t mod 2
  t <- t div 2
od
```
  2. invariant n = t*2^k + m, where m is the number represented by b[1..k].
  3. true before the start because t = n and k = 0.
  4. true on after each iteration - t even or odd
  5. after the loop t = 0 and so n = m

This page last modified on 2 November 1999.