Discussion 1A

Induction

Prove that for all , holds.

Weak induction steps:

  1. Base case: Prove that holds
  2. Inductive hypothesis: Assume that holds for some value of
  3. Inductive step: Show that holds under the inductive hypothesis

Strong induction steps:

  1. Base case: Prove that holds
  2. Inductive hypothesis: Assume that holds for all values of between and
  3. Inductive step: Show that holds under the inductive hypothesis

Applications

minor typo on 1b: