Discussion 1A

Induction

Prove that for all nNn \in \mathbb{N}, P(n)P(n) holds.

Weak induction steps:

  1. Base case: Prove that P(0)P(0) holds
  1. Inductive hypothesis: Assume that P(k)P(k) holds for some value of kk
  1. Inductive step: Show that P(k+1)P(k+1) holds under the inductive hypothesis

Strong induction steps:

  1. Base case: Prove that P(0)P(0) holds
  1. Inductive hypothesis: Assume that P(n)P(n) holds for all values of nn between 00 and kk
  1. Inductive step: Show that P(k+1)P(k+1) holds under the inductive hypothesis

Applications

  • Divide and conquer/recursion problems
  • Binary search, sorting
  • Graphs
  • Trees

minor typo on 1b: 12+22+32+1^2 + 2^2 + 3^2 + \cdots