📂Set Theory

Mathematical Induction

Law ¹

$$\left[ p(1) \land \left( p(n) \implies p(n+1) \right) \right] \implies \forall n \in \mathbb{N} : p(n)$$ Regarding the proposition $p(n) (n=1,2,3, \cdots )$, if $p(1)$ is true and assuming $p(n)$, then if $p(n+1)$ holds, $p(n)$ is true.

Explanation

When a formula holds for natural numbers, a powerful proof method called Peano’s Fifth Axiom is especially potent, or simply called induction without the ‘mathematical’ prefix. Originally, induction refers to deriving certain conclusions by empirically collecting phenomena or entities, but in mathematics, it’s understood as mathematical induction without explanation.

Mathematical induction seems difficult to understand at first but becomes extremely easy once understood. As can be inferred from its alias, Peano’s Fifth Axiom, it’s considered an axiom because it’s inherently logical. Mathematical Induction Mathematical induction is often likened to dominoes:

• (1) The first domino falls. It’s an apparent fact that the first domino falls, simply because you topple it yourself. Similarly, in proofs, this is usually shown easily by substituting $1$ into the proposition.
• (2) The falling of a previous domino topples the next one. If the $n$th domino falls, it topples the $(n+1)$th domino as well. In a row of dominoes, the notion that a domino would topple the next one is plausible. Demonstrating this is the essence and the most challenging part of mathematical induction.
• **(3) If the above is true, toppling the first domino results in all dominoes falling.
  • Let’s say you’ve toppled the first domino.
  • Accordingly, from (2), the $1$th domino topples the $2$th domino.
  • Again, from (2), the $2$th domino in turn topples the $3$th domino.
  • And again, from (2), the $n$th domino in turn topples the $(n+1)$th domino.
  • Thus, all dominoes topple the next leading to every single domino falling, no matter how many there are.

Returning to mathematical induction, when $p(1)$ holds, so does $p(1+1)$, meaning $p(2)$ holds. When $p(2)$ holds, $p(2+1)$ holds, and when $p(n)$ holds, $p(n+1)$ holds.

But isn’t assuming $p(n)$ a circular argument?

It can be confusing why one might assume $p(n)$ holds when first encountering mathematical induction, and I too was puzzled by this in high school. However, what we are actually demonstrating is not that $p(n)$ itself holds, but that if $p(n)$ holds, then $p(n+1)$ also holds. Therefore, mathematical induction is considered a form of indirect proof.

• Frankly, it doesn’t matter whether $n$ holds for all cases or not. If a false conclusion is drawn from a false assumption, the logic in-between is sound.
• If it holds true, then $p(1)$ holds, thus it applies to all natural numbers. This is the true conclusion of the proof. At least one true proposition $p(1)$ must exist to justify the validity of $p(n)$ for all natural numbers.