Mathematical induction

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.

Description

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.

Extended proofs

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.

Comparison with inductive reasoning

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.

See also

• Combinatorial proof
• Computer science
• Direct proof
• Mathematical logic
• Mathematical proof
• Recursion
• Recursion (computer science)
• Structural induction
• Well-order

External links

• Mathematical induction @ Wikipedia