SUNY Geneseo Department of Computer Science

Induction, Part 2

Previous Lecture

Misc

Hand out Lab 5

Questions?

Third problem in lab 4 (counting red tiles)

• Hitting a robot is an obstruction
• Pick a path to test that has no other robots

Induction Example

Play-act the proof that sum of first n naturals = n(n+1)/2

(See book for proof)

People in class "proved" that this theorem holds for specific values of n. First had to do the arithmetic (induction's base case), but others could all just point to the fact that we know that whenever the theorem is true of one number it's true of the next, and to the fact that it was true for the previous person, to make their case (induction step, which must apply to any number and its successor in general).

Template for induction proof:

• Base case: plug small number (e.g., 0, 1) in to theorem
• Induction:
  • Hypothesis: plug k-1 in to theorem, assume true
  • Show... plug k in to theorem

Example

Mini-Assignment: Use induction to show that whenever n >= 4, n! > 2ⁿ

Base case: n = 4.

• 4! > 2⁴?
• 24 > 2⁴?
• 24 > 16?
• Yes!

Induction

• Assume (k-1)*(k-2)...*2*1 > 2^k-1
  • where k-1 >= 4
  • [ (k-1)! = product of integers from 1 to k-1 ]
• Show k! > 2^k
  • k*(k-1)*(k-2)*...*2*1 > 2^k
  • k*(k-1)*(k-2)*...*2*1 > 2 * 2^k-1
    • [ a^x * a^y = a^x+y, a = 2 x=1, y=k-1 ]
  • a * b > c * d whenever a > c and b > d

Connection to Recursion

Recursion in an algorithm uses a small problem to solve bigger one

Induction step uses knowledge about a small theorem to prove a bigger one

To prove (or discover) something about recursive case assume the algorithm works for small problem, prove (or figure out) how that solves a bigger problem

Base cases solve/prove smallest problems/theorems, in order to get things started

Next

Read Section 7.1.2

Next Lecture