SUNY Geneseo Department of Computer Science

Introduction to Induction

Previous Lecture

Misc

Voter registration and information Tuesday, Sept. 28, 11:00 - 8:30, College Union

I won't be here Monday (Sept. 27); lab will be "open lab" format (do at your own pace/time; ask questions via office hours, lecture, etc.)

Hand out Lab 4

Questions?

Reading Summary

Section 7.1 through the "Introduction" part of 7.1.2 (top of page 216)

Analysis of recursion via induction

Outline of induction

• Base case, make sure it's true
• Assume algorithm true for k-1
• Show it holds for k using this assumption

Domino effect

(Implicit induction

• Parameter to induction is implied, e.g., ok to move

Strong and weak induction

• Strong induction assumption is for all values less than k, base case shows this
• Weak induction makes assumption for k-1)

Mathematical Induction

Use induction to prove that 3ⁿ is odd, for all natural numbers n

• Form of induction
• Base case: (Prove the theorem for the smallest value)
  • n = 1. Is 3¹ odd?
    • 3¹ = 3 which is of form 2i+1, i.e., odd
  • (for purposes of CS, define "natural number" as whole number >=0)
  • n = 0 is also a base case
    • 3⁰ is odd?
    • 3⁰ = 1, which is odd
• Induction Hypothesis:
  • (Assume the theorem is true for some number....)
  • Assume 3^k is odd
• Induction:
  • (...then see if theorem holds for the next number, in which case it really holds for all larger numbers)
  • Show 3^k+1 is odd
  • 3^k+1 = 3^k * 3¹ = 3^k * 3
  • 3^k is odd (from induction hypothesis)
  • 3 is odd
  • odd * odd is odd (from number theory)

Use induction to prove that for all n >= 4, n! > 2ⁿ

• (Why would anyone care? Because algorithms with execution times proportional to 2ⁿ are generally considered so slow as to be useless, but some interesting algorithms have execution times proportional to n! - the above proves that those algorithms are also generally useless)
• n! = n * (n-1) * (n-2) * ... * 2
• Why k -> k+1 vs k-1 -> k?
  • Assumption about smaller number, proof about the next number
  • k-1 -> k matches recursion better
• Base case, n = 4
  • Check if n >= 4, it is
  • Check if n! > 2ⁿ,
  • 4! = 4 * 3 * 2 * 1
  • 2⁴ = 2 * 2 * 2 * 2
  • = 4 * 2 * 2 < 4 * 3 * 2
• Assume n! > 2ⁿ
• Show (n+1)! > 2ⁿ⁺¹ (theorem, applied to n+1)
  • n! * (n+1) > 2ⁿ * 2 (def. factorial, and exponentiation)
  • n+1 > 2 ?
    • (induction hypothesis, n! > 2ⁿ implies theorem true if n+1 > 2)
  • n+1 is > 2 because n >= 4
  • or...
    • n! * (n+1) > 2ⁿ * 2
    • True because n! > 2ⁿ (induction hypothesis)
      • and (n+1) > 2 (n >= 4)

Induction and Recursive Algorithms

Prove last week's algorithm for initializing a SuperArray correct

    // In class SuperArray...
    init( int i )
        if i >= 0
            A[i] = 0
            this.init( i - 1 )

Postcondition: A[0] = A[1] = ... = A[i] = 0

Base case, i = 0

• i >= 0 test succeeds
• A[i] set to 0
• ...

Or base case, i = -1

• Corresponds to base case in algorithm
• " if i >= 0" test fails,
• Algorithm does nothing
• Postcondition: all elements of A between positions 0 and i are 0
• Here, all positions between 0 and -1
• Vacuous truth: anything is true of all elements of an empty set

Do induction part as mini-assignment

Next

Inductive proofs about recursive algorithms

Read remainder of Section 7.1 (i.e., top of page 216 through top of page 222)

Next Lecture