SUNY Geneseo Department of Computer Science

Induction and Algorithms, Part 1

Return to List of Lectures

Misc

Problem set 4 due today

Phi Beta Kappa Lecture

• David Kendall, "The Great War Today"
• Monday, Feb. 5, 4:30 PM, Newton 203

Questions?

Induction - how to algebraically get final result in induction step?

• Prove by induction sum of first n even numbers = n² + n
  • i.e., 2 + 4 + 6 + .... + 2n = n² + n
  • Form
    • Base case
      • is 2 (sum of the first 1 even numbers, i.e., ... + 2x1)
      • = 1² + 1
      • = 1 + 1 = 2
    • Induction Step
      • Induction hypothesis (about k-1)
        • Assume your theorem is true of k-1
        • i.e., assume 2 + 4 + 6 + .... 2(k-1) = (k-1)² + (k-1)
      • Show the theorem is true of k
        • i.e., 2 + 4 + 6 + ... +2(k-1) + 2k = k² + k
        • 1. Use induction hypothesis to remove/simplify something in goal
        • 2. Use algebra or other logic not depending on induction hypothesis to rewrite what's left to show equivalence of left and right sides
        • 2 + 4 + 6 + ... +2(k-1) + 2k
        • = (k-1)² + (k-1) + 2k
        • = k² - 2k + 1 + k - 1 + 2k
        • = k² + k

Reasoning about Recursion

Section 7.1.2

• Induction, examples
• What was the point?
  • Different uses of recursion, e.g., side-effect vs returning values
  • Induction as the reason why recursive algorithms work
• Strong induction
  • Stronger cases, stronger assumptions, assume theorem for all numbers k-1 or less, not just k-1

Example

• Prove that the following algorithm prints the integers from n down to 0, given the precondition that n is an integer greater than or equal to 0

        printDown( n )
        if n > 0
            print n
            printDown( n - 1 )
        else
            print 0

• Theorem: printDown(n) prints integers from n down to 0
• By induction on n (thing that gets smaller in recursion)
• Base case, n = 0
  • Does algorithm print 0?
    • "if n > 0" fails, algorithm executes "else"
    • Prints 0
    • Algorithm done
  • Proof's base case deals with algorithm's base case
• Induction step
  • Induction hypothesis about k-1
    • Assume printDown(k-1) prints integers from k-1 down to 0
  • Show theorem about k
    • printDown(k) prints integers from k down to 0
    • k > 0, because printDown(k-1) defined, so k-1 ≥ 0, k > 0
    • "if n > 0" succeeds
    • printDown prints k
    • Then calls printDown(k-1), which by induction hypothesis prints k-1 down to 0
    • Collectively, k down to 0 has been printed
  • Induction step dealt with recursive case

Hand out problem set 5

Next

Keep applying induction to recursive algorithms