Namespaces
Variants
Actions

Difference between revisions of "Mathematical induction"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fix tex)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A method of proving mathematical results based on the principle of mathematical induction: An assertion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626401.png" />, depending on a natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626402.png" />, is regarded as proved if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626403.png" /> has been proved and if for any natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626404.png" /> the assumption that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626405.png" /> is true implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626406.png" /> is also true.
+
{{TEX|done}}
 +
A method of proving mathematical results based on the principle of mathematical induction: An assertion $A(x)$, depending on a natural number $x$, is regarded as proved if $A(1)$ has been proved and if for any natural number $n$ the assumption that $A(n)$ is true implies that $A(n+1)$ is also true.
  
The proof of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626407.png" /> is the first step (or base) of the induction and the proof of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626408.png" /> from the assumed truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m0626409.png" /> is called the induction step. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264010.png" /> is called the induction parameter and the assumption of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264011.png" /> for the proof of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264012.png" /> is called the induction assumption or induction hypothesis. The principle of mathematical induction is also the basis for [[Inductive definition|inductive definition]]. The simplest example of such a definition is the definition of the property:  "to be a word of length n over a given alphabet a1…ak" .
+
The proof of $A(1)$ is the first step (or base) of the induction and the proof of $A(n+1)$ from the assumed truth of $A(n)$ is called the induction step. Here $n$ is called the induction parameter and the assumption of $A(n)$ for the proof of $A(n+1)$ is called the induction assumption or induction hypothesis. The principle of mathematical induction is also the basis for [[Inductive definition|inductive definition]]. The simplest example of such a definition is the definition of the property:  "to be a word of length $n$ over a given alphabet $\{a_1,\ldots,a_k\}$".
  
The base of the induction is: Each symbol of the alphabet is a word of length 1. The induction step is: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264013.png" /> is a word of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264014.png" />, then each word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264016.png" />, is a word of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264017.png" />. Induction can also start at the zero-th step.
+
The base of the induction is: Each symbol of the alphabet is a word of length 1. The induction step is: If $E$ is a word of length $n$, then each word $Ea_i$, where $1\leq i\leq k$, is a word of length $(n+1)$. Induction can also start at the zero-th step.
  
It often happens that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264019.png" /> can be proved by similar arguments. In these cases it is convenient to use the following equivalent form of the principle of mathematical induction. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264020.png" /> is true and if for each natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264021.png" /> from the assumption: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264022.png" /> is true for any natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264023.png" />, it follows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264024.png" /> is also true for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264025.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264026.png" /> is true for any natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264027.png" />. In this form the principle of mathematical induction can be applied for proving assertions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264028.png" /> in which the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264029.png" /> runs through any well-ordered set of a transfinite type ([[Transfinite induction|transfinite induction]]). As simple examples of transfinite induction one has induction over a parameter running through the set of all words over a given alphabet with the lexicographic ordering, and induction over the construction formulas in a given logico-mathematical calculus.
+
It often happens that $A(1)$ and $A(n+1)$ can be proved by similar arguments. In these cases it is convenient to use the following equivalent form of the principle of mathematical induction. If $A(1)$ is true and if for each natural number $n$ from the assumption: $A(x)$ is true for any natural number $x<n$, it follows that $A(x)$ is also true for $x=n$, then $A(x)$ is true for any natural number $x$. In this form the principle of mathematical induction can be applied for proving assertions $A(x)$ in which the parameter $x$ runs through any [[well-ordered set]] of a transfinite type ([[Transfinite induction|transfinite induction]]). As simple examples of transfinite induction one has induction over a parameter running through the set of all words over a given alphabet with the lexicographic ordering, and induction over the construction formulas in a given logico-mathematical calculus.
  
Sometimes, for the inductive proof of an assertion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264030.png" /> one has to inductively prove, simultaneously with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264031.png" />, a whole series of other results without which the induction for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264032.png" /> cannot be carried out. In formal arithmetic one can also give results <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264033.png" /> for which, within the limits of the calculus considered, an induction can not be carried out without the addition of new auxiliary results depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264034.png" /> (see [[#References|[3]]]). In these cases one has to deal with the proof of a number of assertions by compound mathematical induction. All these statements could formally be united into one conjunction; however, in practice this would only complicate the discussion and the possibility of informal sensible references to specific induction assumptions would disappear.
+
Sometimes, for the inductive proof of an assertion $A(n)$ one has to inductively prove, simultaneously with $A(n)$, a whole series of other results without which the induction for $A(n)$ cannot be carried out. In formal arithmetic one can also give results $A(n)$ for which, within the limits of the calculus considered, an induction can not be carried out without the addition of new auxiliary results depending on $n$ (see [[#References|[3]]]). In these cases one has to deal with the proof of a number of assertions by compound mathematical induction. All these statements could formally be united into one conjunction; however, in practice this would only complicate the discussion and the possibility of informal sensible references to specific induction assumptions would disappear.
  
 
In some concrete mathematical investigations the number of notions and results defined and proved by compound induction has reached three figures (see [[#References|[4]]]). In this case, because of the presence in induction of a large number of cross references to the induction assumptions, for a concise (informal) understanding of any (even very simple) definition or results for a large value of the induction parameter, the reader must be familiar with the content of all induction ideas and properties of these ideas for small values of the induction parameter. Apparently, the only logically correct outcome of this circle of problems is the axiomatic presentation of all these systems of ideas. Thus, a great number of ideas defined by compound mathematical induction lead to the need for an application of the [[Axiomatic method|axiomatic method]] in inductive definitions and proofs. This is a visual example of the necessity of the axiomatic method for the solution of concrete mathematical problems, and not just for questions relating to the foundations of mathematics.
 
In some concrete mathematical investigations the number of notions and results defined and proved by compound induction has reached three figures (see [[#References|[4]]]). In this case, because of the presence in induction of a large number of cross references to the induction assumptions, for a concise (informal) understanding of any (even very simple) definition or results for a large value of the induction parameter, the reader must be familiar with the content of all induction ideas and properties of these ideas for small values of the induction parameter. Apparently, the only logically correct outcome of this circle of problems is the axiomatic presentation of all these systems of ideas. Thus, a great number of ideas defined by compound mathematical induction lead to the need for an application of the [[Axiomatic method|axiomatic method]] in inductive definitions and proofs. This is a visual example of the necessity of the axiomatic method for the solution of concrete mathematical problems, and not just for questions relating to the foundations of mathematics.
Line 17: Line 18:
  
 
====Comments====
 
====Comments====
In the article above, the natural numbers are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264035.png" /> (i.e. excluding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062640/m06264036.png" />).
+
In the article above, the natural numbers are $1,2,\ldots$ (i.e. excluding $0$).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Maclane,  G. Birkhoff,  "Algebra" , Macmillan  (1967)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Maclane,  G. Birkhoff,  "Algebra" , Macmillan  (1967)</TD></TR></table>

Latest revision as of 19:52, 15 January 2021

A method of proving mathematical results based on the principle of mathematical induction: An assertion $A(x)$, depending on a natural number $x$, is regarded as proved if $A(1)$ has been proved and if for any natural number $n$ the assumption that $A(n)$ is true implies that $A(n+1)$ is also true.

The proof of $A(1)$ is the first step (or base) of the induction and the proof of $A(n+1)$ from the assumed truth of $A(n)$ is called the induction step. Here $n$ is called the induction parameter and the assumption of $A(n)$ for the proof of $A(n+1)$ is called the induction assumption or induction hypothesis. The principle of mathematical induction is also the basis for inductive definition. The simplest example of such a definition is the definition of the property: "to be a word of length $n$ over a given alphabet $\{a_1,\ldots,a_k\}$".

The base of the induction is: Each symbol of the alphabet is a word of length 1. The induction step is: If $E$ is a word of length $n$, then each word $Ea_i$, where $1\leq i\leq k$, is a word of length $(n+1)$. Induction can also start at the zero-th step.

It often happens that $A(1)$ and $A(n+1)$ can be proved by similar arguments. In these cases it is convenient to use the following equivalent form of the principle of mathematical induction. If $A(1)$ is true and if for each natural number $n$ from the assumption: $A(x)$ is true for any natural number $x<n$, it follows that $A(x)$ is also true for $x=n$, then $A(x)$ is true for any natural number $x$. In this form the principle of mathematical induction can be applied for proving assertions $A(x)$ in which the parameter $x$ runs through any well-ordered set of a transfinite type (transfinite induction). As simple examples of transfinite induction one has induction over a parameter running through the set of all words over a given alphabet with the lexicographic ordering, and induction over the construction formulas in a given logico-mathematical calculus.

Sometimes, for the inductive proof of an assertion $A(n)$ one has to inductively prove, simultaneously with $A(n)$, a whole series of other results without which the induction for $A(n)$ cannot be carried out. In formal arithmetic one can also give results $A(n)$ for which, within the limits of the calculus considered, an induction can not be carried out without the addition of new auxiliary results depending on $n$ (see [3]). In these cases one has to deal with the proof of a number of assertions by compound mathematical induction. All these statements could formally be united into one conjunction; however, in practice this would only complicate the discussion and the possibility of informal sensible references to specific induction assumptions would disappear.

In some concrete mathematical investigations the number of notions and results defined and proved by compound induction has reached three figures (see [4]). In this case, because of the presence in induction of a large number of cross references to the induction assumptions, for a concise (informal) understanding of any (even very simple) definition or results for a large value of the induction parameter, the reader must be familiar with the content of all induction ideas and properties of these ideas for small values of the induction parameter. Apparently, the only logically correct outcome of this circle of problems is the axiomatic presentation of all these systems of ideas. Thus, a great number of ideas defined by compound mathematical induction lead to the need for an application of the axiomatic method in inductive definitions and proofs. This is a visual example of the necessity of the axiomatic method for the solution of concrete mathematical problems, and not just for questions relating to the foundations of mathematics.

References

[1] D. Hilbert, P. Bernays, "Grundlagen der Mathematik" , 1–2 , Springer (1968–1970)
[2] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[3] L.L. [L.L. Tsinman] Cinman, "On the role of the principle of induction in a formal arithmetic system" Math. USSR Sb. , 6 : 1 (1968) pp. 65–95 Mat. Sb. , 77 : 1 (1968) pp. 71–104
[4] S.I. Adyan, "The Burnside problem and identities in groups" , Springer (1979) (Translated from Russian)


Comments

In the article above, the natural numbers are $1,2,\ldots$ (i.e. excluding $0$).

References

[a1] S. Maclane, G. Birkhoff, "Algebra" , Macmillan (1967)
How to Cite This Entry:
Mathematical induction. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Mathematical_induction&oldid=18312
This article was adapted from an original article by S.I. Adyan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article