Induction

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

Weak induction steps:

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

Strong induction steps:

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

Applications

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

minor typo on 1b: \(1^2 + 2^2 + 3^2 + \cdots\)