Second Principle of Mathematical Induction/Predicate

From ProofWiki
Jump to: navigation, search

Theorem

Let $P \left({n}\right)$ 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 P \left({n_0}\right)$ is true
$(2): \quad \forall k \in \N: k \ge n_0: P \left({n_0}\right) \land P \left({n_0 + 1}\right) \land \ldots \land P \left({k-1}\right) \land P \left({k}\right) \implies P \left({k+1}\right)$

Then:

$P \left({n}\right)$ is true for all $n \ge n_0$.


This process is called proof by (mathematical) induction.


Proof

For each $n \ge n_0$, let $P' \left({n}\right)$ be defined as:

$P' \left({n}\right) := P \left({n_0}\right) \land \dots \land P \left({n}\right)$

It suffices to show that $P' \left({n}\right)$ is true for all $n \ge n_0$.


It is immediate from the assumption $P \left({n_0}\right)$ that $P' \left({n_0}\right)$ is true.

Now suppose that $P' \left({n}\right)$ holds.

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

Consequently, $P' \left({n}\right) \land P \left({n+1}\right) = P' \left({n + 1}\right)$ holds.


Thus by the Principle of Mathematical Induction:

$P' \left({n}\right)$ holds for all $n \ge n_0$

as desired.

$\blacksquare$


Sources