Karl Jones: Created page with "'''Mathematical induction''' is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it c..."

2016-08-25T15:50:07Z

Created page with "'''Mathematical induction''' is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it c..."

New page

'''Mathematical induction''' is a [[mathematical proof]] technique, most commonly used to establish a given statement for all [[Natural number|natural numbers]], although it can be used to prove statements about any [[Well-order|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 (computer science)|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 ==

* [https://en.wikipedia.org/wiki/Mathematical_induction# Mathematical induction] @ Wikipedia

[[Category:Mathematics]]

Mathematical induction - Revision history

Karl Jones: Created page with "'''Mathematical induction''' is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it c..."