Mathematical induction - Imported Knowlpedia Content

Mathematical induction: Let $P(n)$ be a statement about $n\in\mathbb{N}$ . If $P(0)$ is true and for every $n\in\mathbb{N}$ the implication $P(n)\Rightarrow P(n+1)$ holds, then $P(n)$ is true for all $n\in\mathbb{N}$ .

Remarks

This is a fundamental method for proving claims indexed by the natural numbers. It is closely connected to the well-ordering principle, and each can be derived from the other in standard foundations.