Second Principle of Mathematical Induction/Algorithm

From ProofWiki
Jump to navigation Jump to search

Algorithm

The Second Principle of Mathematical Induction can be implemented as an algorithm as follows.

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

Let it be established that:

$\text{(a)}: \quad \map P 1$ is true
$\text{(b)}: \quad$ If all of $\map P 1, \map P 2, \ldots, \map P k$ are true, then $\map P {k + 1}$ is true.

Then the following algorithm provides a proof of $\map P k$ for all $n \in \N$:


$\mathbf 1:$ Prove $\map P 1$.
Set $k \gets 1$ and prove $\map P 1$ according to $\text{(a)}$.
$\mathbf 2:$ Is $k = n$?.
If $k = n$ then terminate. The required proof has been output.
$\mathbf 3:$ Prove $\map P {k + 1}$.
According to $\text{(b)}$, output a proof that if all of $\map P 1, \map P 2, \ldots, \map P k$ are true, then $\map P {k + 1}$ is true.
$\mathbf 4:$ Increase $k$.
$k \gets k + 1$ and to to step $\mathbf 2$.


Sources