Principle of Mathematical Induction

From ProofWiki
Jump to: navigation, search

Contents

Theorem

Let $P \left({n}\right)$ be a propositional function depending on $n \in \N$.


If the following statements hold:

$(1): \quad P \left({n_0}\right)$ is true for some $n_0 \in \N$ (where $n_0$ is often, but not always, zero or one)
$(2): \quad \forall k \in \N: k \ge n_0 : 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.


Basis for the Induction

The step that shows that the proposition is true for the first value $n_0$ is called the basis for the induction (also sometimes informally called the base case).


Induction Hypothesis

The assumption made that $P \left({k}\right)$ is true for some $k \in \N$ is the induction hypothesis (also sometimes called the inductive hypothesis).


Induction Step

The step which shows that $P \left({k}\right) \implies P \left({k+1}\right)$ is called the induction step (also sometimes called the inductive step).


Proof

Suppose that the two given conditions hold:

$(1): \quad P \left({n_0}\right)$ is true for some $n_0 \in \N$
$(2): \quad \forall k \in \N: k \ge n_0 : P \left({k}\right) \implies P \left({k+1}\right)$


Let $S = \left\{{x \in \N: P \left({x}\right)}\right\}$.

That is, the set of all $x \in \N$ for which $P \left({x}\right)$ holds.

From Subset of Set with Propositional Function, $S \subseteq \N$.

We have that $n_0 \in S$ from $(1)$.

Now suppose $k \in S$.

That is, $P \left({k}\right)$ holds.

From $(2)$ it follows that $P \left({k + 1}\right)$ holds, and so $k + 1 \in S$.

Thus we have established:

$S \subseteq \N$
$n_0 \in S$
$k \in S \implies k + 1 \in S$

From the Principle of Finite Induction it follows that $\N \setminus \N_{n_0} \subseteq S$.

That is, for every element $k$ of $\N \setminus \N_{n_0}$, it follows that $P \left({k}\right)$ holds.

But $\N \setminus \N_{n_0}$ is precisely the set of all $n \in \N$ such that $n \ge n_0$.

Hence the result.

$\blacksquare$


Minimal Infinite Successor Set

In the language of the minimal infinite successor set, this principle can be written as:

If:

$(1): \quad P \left({n_0}\right)$ is true for some $n_0 \in \omega$ (where $n_0$ is often, but not always, zero or one)
$(2): \quad \forall k \in \omega: k \ge n_0 : P \left({k}\right) \implies P \left({k^+}\right)$

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


Here, $k^+$ denotes the successor of $k$, and $\omega$ denotes the minimal infinite successor set.


Comment

Note the difference between this and the Second Principle of Mathematical Induction, which can often be used when it is not possible to prove $P \left({k+1}\right)$ directly from the truth of $P \left({k}\right)$, but when it is possible to prove $P \left({k+1}\right)$ from the assumption of the truth of $P \left({n}\right)$ for all values of $n_0$ such that $n_0 \le n \le k$.


This principle is sometimes referred to as the Principle of Weak Induction.


In Equivalence of Well-Ordering Principle and Induction it is proved that this, the Second Principle of Mathematical Induction and the Well-Ordering Principle are all logically equivalent to each other.


Sources

  • For a video presentation of the contents of this page, visit the Khan Academy.
Retrieved from "http://www.proofwiki.org/w/index.php?title=Principle_of_Mathematical_Induction&oldid=143759"