Second Principle of Mathematical Induction/Predicate

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $n_0 \in \N$ be given. ($n_0$ is often, but not always, zero or one.)


Suppose that:

$(1): \quad \map P {n_0}$ is true
$(2): \quad \forall k \in \N: k \ge n_0: \map P {n_0} \land \map P {n_0 + 1} \land \ldots \land \map P {k - 1} \land \map P k \implies \map P {k + 1}$

Then:

$\map P n$ is true for all $n \ge n_0$.


This process is called proof by (mathematical) induction.


Proof

For each $n \ge n_0$, let $\map {P'} n$ be defined as:

$\map {P'} n := \map P {n_0} \land \dots \land \map P n$

It suffices to show that $\map {P'} n$ is true for all $n \ge n_0$.


It is immediate from the assumption $\map P {n_0}$ that $\map {P'} {n_0}$ is true.

Now suppose that $\map {P'} n$ holds.

By $(2)$, this implies that $\map P {n + 1}$ holds as well.

Consequently, $\map {P'} n \land \map P {n + 1} = \map {P'} {n + 1}$ holds.


Thus by the Principle of Mathematical Induction:

$\map {P'} n$ holds for all $n \ge n_0$

as desired.

$\blacksquare$


Sources