Proof by Induction

Overview

• 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)$$