Induction

If a statement is true for a specific case $P(a)$ and it is true that the truth of some case after $a$ implies the truth of its subsequent case, then the statement must be true for all cases at and after $a$.

If we show that the first domino can be knocked down, and that for an arbitrary domino after the first, if it is knocked down then so too does the domino after it, then all dominos must be knocked down.

If we show that the first domino can be knocked down, and that for an arbitrary domino after the first, if it is knocked down then so too does the domino after it, then all dominos must be knocked down.

At the core of induction is the Well Ordering Principle, which states that any nonempty subset of the natural numbers always has a smallest element. If this weren’t the case, then there would be no valid implication for the induction step, and thus induction would be impossible!

Weak Induction

Formal statement of the principle of induction.

<aside> 💡

If an arbitrary domino falls, does this imply that the next domino will fall?

</aside>

  1. Base Case. Show that $P$ holds for a specific $a$.
  2. Inductive Hypothesis. Assume that for some $k \geq a$, $P$ holds for $k$.
  3. Inductive Step. Prove that $P(k) \rightarrow P(k+1)$.

Strong Induction

If a stronger hypothesis is ever needed, this strengthens weak induction by assuming that the inductive hypothesis holds for all values between $a$ and $k$.

<aside> 💡

If all dominos before an arbitrary domino fall along with it, does this imply that the next domino will fall?

</aside>

  1. Base Case. Show that $P$ holds for a specific $a$.
  2. Inductive Hypothesis. Assume $P(a) \wedge \dots \wedge P(k)$.
  3. Inductive Step. Prove that $P(a) \wedge \dots \wedge P(k) \rightarrow P(k+1)$.

The reason why were are allowed to assume that $P$ holds over a range up to $k$ is because weak induction would have proved the same thing. In other words, strong induction can simply be seen as the result of applying weak induction repeatedly.