Second Principle of Mathematical Induction/Algorithm
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 3:$ Prove $\map P {k + 1}$.
- $\mathbf 4:$ Increase $k$.
- $k \gets k + 1$ and to to step $\mathbf 2$.
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction