Third Principle of Mathematical Induction

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\map P n$ be a propositional function depending on $n \in \N$.

If:

$(1): \quad \map P n$ is true for all $n \le d$ for some $d \in \N$
$(2): \quad \forall m \in \N: \paren {\forall k \in \N, m \le k < m + d: \map P k} \implies \map P {m + d}$

then $\map P n$ is true for all $n \in \N$.


Proof

Let $A = \set {n \in \N: \map P n}$.

We show that $A$ is an inductive set.

By $(1)$:

$\forall 1 \le i \le d: i \in A$

Let:

$\forall x \ge d: \set {1, 2, \dotsc, x} \subset A$

Then by definition of $A$:

$\forall k \in \N: x - \paren {d - 1} \le k < x + 1: \map P k$

Thus $\map P {x + 1} \implies x + 1 \in A$

Thus $A$ is an inductive set.

Thus by the fifth axiom of Peano:

$\forall n \in \N: A = \N \implies \map P n$

$\blacksquare$


Sources