What is "mathematical induction"

n. (context mathematics English) A method of proof which, in terms of a predicate ''P'', could be stated as: if $P(0)$ is true and if for any natural number $n\; ge\; 0$, $P(n)$ implies $P(n\; +\; 1)$, then $P(n)$ is true for any natural number ''n''.

Mathematical induction is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it can be used to prove statements about any well-ordered set. It is a form of direct proof, and it is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs.

Although its name may suggest otherwise, mathematical induction should not be misconstrued as a form of inductive reasoning (also see Problem of induction). Mathematical induction is an inference rule used in proofs. In mathematics, proofs including those using mathematical induction are examples of deductive reasoning, and inductive reasoning is excluded from proofs.