Proof by Induction


  • Induction can refer to weak induction, strong induction or structural induction
    • In all cases, induction is a method to prove a statement \(P(x)\) about a “complex” element \(x\) of a set by reducing it to a “simpler case”
  • The predicate \(P(x)\) is often referred to as “inductive hypothesis”

Weak Induction

  • If \(P(n)\) is a statement, and we wish to prove “\(\forall n \in \mathbb{N}: P(n)\)”, one way is to use weak induction

To prove “\(\forall n \in \mathbb{N}: P(n)\)” using weak induction, we prove \(P(0)\), and then we must prove \(P(n + 1)\) for an arbitrary \(n\) under the assumption \(P(n)\)

  • \(P(0)\) is called the base case
  • \(P(n + 1)\) is called inductive step
  • \(P(n)\) is called induction hypothesis

Strong Induction

  • To prove “\(\forall n \in \mathbb{N}: P(n)\)” by strong induction, we must
    • Prove \(P(0)\)
    • For arbitrary \(n\), prove \(P(n)\) under the assumption \(P(n - 1), P(n - 2), \dots, P(0)\)
    • The induction step requires to prove \(P(n)\) assuming \(P(k), \forall k < n\)
  • The difference between strong induction and weak induction is only the set of assumptions made in the inductive step
  • We can always use strong induction instead of weak induction
    • By using weak induction we avoid unneeded assumptions and reduce the complexity of the proof
    • In fact, we can convert a proof by strong induction into a proof by weak induction by strengthening the inductive hypothesis

Strengthening the Inductive Hypothesis

  • Sometimes the induction hypothesis does not say enough to be applicable in the inductive step
    • In this case it might be “easier” (lul) to prove a stronger result
    • Here we actually prove more but that means we have more facts available in the inductive step
  • \(\forall k \leq n: P(k)\)