Argument
Mathematical induction
Overview
Mathematical induction is a method for proving that a statement
P
(
n
)
{\displaystyle P(n)}
is true for every natural number
n
{\displaystyle n}
, that is, that the infinitely many cases
P
(
0
)
,
P
(
1
)
,
P
(
2
)
,
P
(
3
)
,
…
{\displaystyle P(0),P(1),P(2),P(3),\dots }
all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).
A proof by induction consists of two cases. The first, the base case, proves the statement for
n
=
0
{\displaystyle n=0}
without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case
n
=
k
{\displaystyle n=k}
, then it must also hold for the next case
n
=
k
+
1
{\displaystyle n=k+1}
. These two steps establish that the statement holds for every natural number
n
{\displaystyle n}
. The base case does not necessarily begin with
n
=
0
{\displaystyle n=0}
, but often with
n
=
1
{\displaystyle n=1}
, and possibly with any fixed natural number
n
=
N
{\displaystyle n=N}
, establishing the truth of the statement for all natural numbers
n
≥
N
{\displaystyle n\geq N}
.
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 is an inference rule used in formal proofs, and is the foundation of most correctness proofs for computer programs.
Despite its name, mathematical induction differs fundamentally from inductive reasoning as used in philosophy, in which the examination of many cases results in a probable conclusion. The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of deductive reasoning involving the variable
n
{\displaystyle n}
, which can take infinitely many values. The result is a rigorous proof of the statement, not an assertion of its probability.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
It is obvious, however, that any hereditary property possessed by Adam must belong to all men; and similarly any hereditary property possessed by 0 must belong to all finite numbers. This is the principle of what is called "mathematical induction." It frequently happens, when we wish to prove that all finite numbers have some property, that we have first to prove that 0 has the property, and then that the property…
Bertrand Russell, Our Knowledge of the External World as a Field for Scientific Method in Philosophy
States what Mathematical induction is; names Mathematical induction.
There are nevertheless, in mathematics, some examples of so-called Induction, in which the conclusion does bear the appearance of a generalization grounded on some of the particular cases included in it. A mathematician, when he has calculated a sufficient number of the terms of an algebraical or arithmetical series to have ascertained what is called the _law_ of the series, does not hesitate to fill up any number…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Mathematical induction is.
Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Mathematical induction is.
Philosophers who discussed Mathematical induction
Related ideas
- First-order logic
- Addison-Wesley
- Golden ratio
- Giuseppe Peano
- Integer
- Problem of induction
- Harvard University
- Augustus De Morgan
- Mathematical logic
- Reflexive relation
- Ivor Grattan-Guinness
- Real number
- Natural number
- Reductio ad absurdum
- Richard Dedekind
- Axiom of infinity
- Peano axioms
- Q.E.D.
- Rule of inference
- Recursion
- Bulletin of the American Mathematical Society
- Set theory
- Predicate (logic)
- Truth
Place in the tradition
Part of Second-order logic.