Mathematical induction is a method for
proving that a statement ''P''(''n'') is true for every
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:
A proof by induction consists of two cases. The first, the base case, proves the statement for ''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'', ''then'' it must also hold for the next case ''n'' = ''k'' + 1. These two steps establish that the statement holds for every natural number ''n''. The base case does not necessarily begin with ''n'' = 0, but often with ''n'' = 1, and possibly with any fixed natural number ''n'' = ''N'', establishing the truth of the statement for all natural numbers ''n'' ≥ ''N''.
The method can be extended to prove statements about more general
well-founded
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s ...
structures, such as
trees; this generalization, known as
structural induction, is used in
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
. Mathematical induction in this extended sense is closely related to
recursion. Mathematical induction is an
inference rule
In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes pr