Complete induction
The induction is a mathematical method of proof , after which a statement for all natural numbers is proved greater than or equal to a start value are. Since there are infinitely many numbers, a derivation cannot be made for each number individually.
The proof that the statement holds for all ( mostly 1 or 0) is therefore carried out in two stages:
- In the beginning of induction , the statement is derived for a smallest number .
- In the induction step is for any the statement from the statement derived.
Or to put it less "mathematically":
- Induction start : It is proven that the statement applies to the smallest number, the starting value.
- Induction step : The following is proven: If the statement applies to any number, it also applies to the number one greater.
Based on the proof for the starting value, the induction step does the proof for all natural numbers above the starting value.
This proof procedure is of fundamental importance for arithmetic and set theory and thus for all areas of mathematics.
Forms of expression
Complete induction deals with the validity of proposition forms .
Example (see Gaussian empirical formula ):
- For
If you substitute values for , you get statements that are true or false.
Obviously, the statements in the example above are all true. Since you cannot recalculate this for all (infinite) numbers, a special proof procedure is required. This provides the whole induction.
The statement form is generally valid if it is true for everyone .
To prove the general validity of the statement form, one shows the following:
- (Start of induction) and
- the statement always follows from the statement (the induction assumption) , and that for all . (This is the induction step.)
illustration
The method of complete induction is comparable to the domino effect : If the first domino falls and the next one is knocked over by each falling domino, each domino in the chain, which is thought to be infinitely long, will eventually fall over.
The general validity of a statement form is proven if is valid (the first stone falls over) and if also applies to (each stone pulls the next stone with it when it falls ).
Etymology and history
The term induction is derived from the Latin inductio , literally "introduction". The addition complete signals that, in contrast to the philosophical induction , which deduces a general law from special cases and is not an exact final procedure, it is a recognized deductive proof procedure.
The induction principle is already latent in the Pythagorean number definition handed down by Euclid : "Number is the set composed of units." Other important mathematicians of antiquity and the Middle Ages also had no need for precise induction proofs. A few exceptions in the Hebrew and Arabic-speaking areas remained without successors.
For a long time, a proof by Franciscus Maurolicus from 1575 was considered the oldest explicit complete induction (detailed below). However, he has not yet discussed the general evidence process. It was Blaise Pascal who first addressed the induction principle with induction beginning and induction step in his Traité du triangle arithmétique from 1654. From 1686 Jakob I Bernoulli contributed significantly to the dissemination of induction proofs .
The proof procedure was then first referred to as induction or successive induction by Augustus De Morgan in 1838 . 1888 finally coined Richard Dedekind in his pamphlet What are and what are the numbers? the term complete induction . Through this work from the early days of set theory , it became a well-known, established principle of proof that no branch of mathematics has been able to do without since then. A year later, in 1889, Giuseppe Peano formulated the first formalized calculus for natural numbers with an induction axiom with the Peanosian axiom, from which the proof scheme of complete induction can be derived. He showed with formal rigor that from his axioms of numbers , to which the axiom of induction belongs, the whole arithmetic down to the real numbers can be derived. Thereby he made the fundamental importance and the power of induction fully aware.
definition
Since Richard Dedekind , complete induction has been defined as follows:
- To prove that a theorem is true for all natural numbers , it suffices to show
- that it applies to and
- that the validity of the proposition for a number always implies its validity for the following number .
As a formal rule of inference with a derivative operator , the complete induction for a statement and a natural number reads :
- and
This final rule is a compact formulation of the proof of the complete induction, which can be formulated in a little more didactically:
- If the formula is to be proven for all natural numbers , then two are sufficientproofsteps:
- the beginning of induction : theproofof ,
- the induction step (also "Enough of on " called): theproofthe inductive claim from and the induction hypothesis (also induction hypothesis , engl. induction hypothesis ) .
- According to the above rule of inference, the generalization of the formula to all natural numbers follows (the final induction conclusion ).
The statement to be proven for natural numbers from a set occurs in at least 3 roles :
(1) as an induction claim for any (single) (2) as an induction requirement for finitely many smaller natural numbers (3) as a general statement to be proven for everyone (and thus for an infinite number)
Usually is or . however, it is possible.
Because the statement for is equivalent to the statement for , Dedekind's induction can be reduced to the complete induction from 0:
The axiomatics of natural numbers by Peano
In 1889, Peano proved with complete induction the basic calculation rules for addition and multiplication : the associative law , commutative law and distributive law .
The axiom of complete induction
Complete induction is an axiom of natural numbers. Mostly, however, it is derived from the equivalent fifth Peano axiom , the induction axiom . This reads:
Is a subset of the natural numbers with the properties:
- is an element of
- With off is always off ,
then is .
The Peano axioms and thus also the proof procedure of complete induction can also be derived from other concepts of natural numbers, for example in the definition of natural numbers
- as an ordered semigroup generated by 1 , which corresponds to the quoted Pythagorean number definition
- as a monoid generated free of 1 , which is based on the addition of the numbers
- as algebra with successor mapping that corresponds to Dedekind's number definition
- as the smallest inductive set , namely as the smallest set that fulfills the axiom of infinity , as is customary in set theory
- as a class of finite ordinal numbers , which only presupposes a general set theory without the axiom of infinity
Examples
Gaussian empirical formula
The Gaussian empirical formula reads: The following applies to all natural numbers
It can be proven by complete induction.
The induction start results immediately:
. |
In the induction step it has to be shown that from the induction hypothesis
the induction claim
For |
follows. This is achieved as follows:
(Main denominator 2) (Exclude from ) (with in the place of )
- (The induction hypothesis is marked in red.)
Finally the induction conclusion: This proves the statement for everyone .
Sum of odd numbers (Maurolicus 1575)
The step-by-step calculation of the sum of the first odd numbers suggests the following: The sum of all odd numbers from to is equal to the square of :
- 1 = 1
- 1 + 3 = 4
- 1 + 3 + 5 = 9
- 1 + 3 + 5 + 7 = 16
The general proposition to be proved is: . Maurolicus proved it in 1575 with complete induction. A proof with calculation rules that are common today reads as follows:
The beginning of induction with is easily checked because of .
As an induction step it is to be shown: If , then . It results from the following chain of equations, in which the induction assumption is applied in the second transformation:
- (The induction hypothesis is marked in red.)
Bernoulli's inequality
The Bernoulli's inequality is for real numbers with and natural numbers
- .
The induction start with applies here because of (whereby the definition gap at this point is supplemented by continuously ).
The induction step is obtained from the following derivation, which uses the induction assumption in the second step, whereby the above condition ensures that the term does not become negative:
- (The induction hypothesis is marked in red.)
The two occurrences of the -sign (in the same direction) can be simplified to:
Equine paradox
The equine paradox is a standard example of an incorrect application of full induction and illustrates the importance of the interplay between induction anchoring and induction step. With him, the nonsensical statement that in a herd of horses all always have the same color is proven by a seemingly correct induction. The induction step itself is correct, but would need the induction anchoring for one , while the (incorrect) proof anchoring the induction at and the step from to fails.
Induction variants
Induction with any beginning
Induction proof of the inequality for natural numbers :
- The induction start for results from .
- The induction step is based on the following derivation, which applies the induction assumption in the second step and the requirement in the fourth and sixth steps :
The finite number of cases that such a more general induction proof does not cover can be examined individually. In the example, the inequality is obviously false.
Strong induction
Induction with several predecessors
In some induction proofs, referring to a single predecessor in the induction hypothesis is not sufficient, for example if a recursion formula contains several predecessors. The induction start must then be carried out for several starting values. If the induction assumption for and is necessary to derive a formula , then an induction start for two consecutive numbers, i.e. for example 0 and 1, is necessary. The statement for all numbers between the starting value and can also serve as an induction requirement . An example is the proof that every natural number has a prime divisor:
- Induction start: 2 is divisible by the prime number 2.
- Induction step: The statement is for all to fulfill. If now is a prime number, it is itself the divisor we are looking for, and the claim is proven. If there is no prime number, there are two numbers with and . In this case, according to the induction assumption (= induction assumption), has a prime divisor, for example . Then divides also and prime-divisor of . This also proves the assertion for this second case.
Formal definition
The statement is valid for all if the following is shown for any :
(Induction step :) .
The proof scheme of strong induction accordingly consists only of the induction step .
The induction step is therefore the proof that | ||
for each | ||
the induction hypothesis | ||
the induction claim | entails. | |
Then the generalization follows | ||
(the induction closure): | The statement applies to everyone . |
Induction beginnings, as they occur in ordinary induction, for example the proof of the statement , are included in the induction step. It can also happen that more than one initial statement has to be shown in advance (see Fibonacci sequence ).
Obviously, the ordinary complete induction (formulated in the introduction) follows from the strong induction. But one can also prove the strong induction with the help of the ordinary complete induction.
proof | ||||||||||
To show is:
We define the following statement for natural numbers and show their validity by means of ordinary complete induction. Induction start: Since , is the empty AND operation , according to the note , it applies immediately. (Ordinary) induction step from to :
With that we have shown which one is, and the usual induction step is done. We conclude (ordinary induction closure):
Because of this, the strong induction conclusion arises a fortiori :
|
Despite this fundamental equivalence in the strength of evidence , the difference in the strength of expression is large because of the unlimited number of starting values and the possibility of falling back on any number of predecessors, especially with recursive definitions . However, this does not mean that the latter definitions cannot be converted into ordinary recursions.
- example
- The result was defined by the recursion . Then: . The strong induction proof is trivial. However, recursion can also easily transform into a to a single predecessor .
Induction with forward-backward steps
In 1821 Augustin-Louis Cauchy demonstrated an induction variant in which the forward induction step makes jumps (namely from to ) and the resulting gaps are subsequently filled in one fell swoop by a backward derivation from to .
Example: Inequality of the arithmetic and geometric mean
Further induction variants
There are also situations where statements about all integers (positive and negative) can be proven with full induction. The proof in the positive direction happens as usual with any induction start and the positive induction step from to . Thereafter it may be possible to carry out the induction step in the negative direction from to . For example, with the Fibonacci sequence, the recursion equation can be turned over in the opposite direction .
The complete induction can be generalized from natural numbers to ordinal numbers . Ordinal numbers that are larger than the natural numbers are called transfinite induction .
The induction can also be transferred to so-called well - founded sets , which have an order structure comparable to the order of numbers; here we sometimes speak of structural induction .
Recursive or inductive definition
The recursive definition - also called inductive definition - is a procedure analogous to complete induction, in which a term is defined by a recursion start and a recursion step.
Example of a recursive function
With the help of complete induction one can prove ( Gaussian sum formula ):
The closed formula saves the laborious recursive calculation.
Conversely, the next example shows that a recursive calculation can be cheaper.
Example of a recursively defined function:
for , for and odd, for and straight.
With the help of complete induction it can be shown that
- for is.
The advantage of this recursive definition is that when calculating high powers one does not have multiplications, but only multiplications in the order of magnitude . Very high potencies are used, for example, for RSA encryption of messages.
The recursive definition, like induction, has all kinds of differentiated variants.
Web links
- http://henked.de/begriffe/induktion.htm Complete induction
- https://www.emath.de/Referate/induktion-lösungen-loesungen.pdf Comprehensive collection of exercises for complete induction
- http://www.kilchb.de/vollstind.php A crash course in complete induction by Joachim Mohr
- Christian Spannagel : Lectures on Complete Induction .
- Full induction evidence vividly explained on video:
Individual evidence
- ↑ Induction start and induction step can often be derived using methods of "school logic". However, full induction is a second order predicate logic method .
- ↑ a b Euclid's Elements VII, Definition 2. In addition: Wilfried Neumaier: Antike Rhythmustheorien , chap. 1 Ancient Mathematical Concepts , pp. 11–12.
- ^ Rabinovitch: Rabbi Levi Ben Gershon and the Origins of Mathematical Induction , in: Archive for History of Exact Sciences 6 (1970), pp. 237-248.
- ↑ Roshdi Rashed : L'induction mathématique: al-Karajī, as-Samaw'al , in: Archive for History of Exact Sciences 9 (1972), pp. 1–21.
- ↑ a b Maurolycus: Arithemticorum Liber primus , p. 7, Proposition 15 a . limited preview in Google Book search.
- ↑ Blaise Pascal: Traité du triangle arithmétique , p. 7, Conséquence douziesme, Le 1. (induction start), Le 2. (induction step), digitally limited preview in the Google book search.
- ^ Lexicon of important mathematicians, Leipzig 1990, article "Jakob Bernoulli", p. 48.
- ↑ De Morgan: Article Induction (Mathematics) in: Penny Cyclopædia XII (1838), pp. 465-466.
- ↑ a b c Richard Dedekind: What are and what are the numbers? , Braunschweig 1888, § 6 sentence 80, original wording: sentence of the complete induction (conclusion from n to n '). In order to prove that a proposition holds for all numbers n in a chain m 0 , it suffices to show that it holds for n = m and that from the validity of the proposition for a number n in the chain m 0 its validity also for the following number n 'follows.
- ^ Peano: Arithmetices principia nova methodo exposita , 1889, in: G. Peano, Opere scelte II, Rome 1958, pp. 20–55.
- ^ Peano: Arithmetices principia nova methodo exposita. 1889. In: G. Peano: Opere scelte. Volume II. Rome 1958. pp. 35-36, 40-41.
- ↑ detailed evidence also in: Edmund Landau : Fundamentals of Analysis. Leipzig 1930.
- ↑ Felscher: Naive sets and abstract numbers I, pp. 130–132.
- ↑ Dedekind: What are and what are the numbers? , § 6, declaration 71.
- ↑ represented as Dedekind triples in: Felscher: Naive Mengen und Abstract Numbers I, p. 147.
- ^ S. Proof of Binet's formula for the Fibonacci sequence
- ↑ Another example is the proof of the Zeckendorf theorem ; s. Zeckendorf's theorem .
-
↑ Is by definition . The induction hypothesis (the induction hypothesis), then, is that for all the numbers from to is assumed to be valid.
- ↑ a b Since the neutral element is the AND connection and therefore the empty AND connection has the truth value , the implication is to be proven by the application of . Viewed in this way, the induction beginning (s) in strong induction are all “stuck” in the induction step.
-
↑ Oliver Deiser Introduction to Mathematics .
The main difference between the strong induction scheme and the ordinary one is - as the proof shows, that in the ordinary scheme each induction assumption is used exactly once (in a single induction level), while in the strong scheme it can be referred to from several higher induction levels. - ↑ Cauchy, Augustin-Louis. Analysis algebrique. Paris 1821. The proof of the inequality of the arithmetic and geometric mean is there on page 457 ff.
- ↑ A forward-backward induction is also the proof of Jensen's inequality . Jensen: Sur les fonctions convexes et les inégalités entre les valeurs moyennes. In: Acta Math. 30, 1906, pp. 175-193.
- ^ Hausdorff: Fundamentals of set theory. 1914. pp. 112–113 limited preview in Google book search.
- ^ Peano: Le Definitions in Matematica. In: Opere scelte. Volume II, 1921. p. 431, § 7 Definizioni per induione.
-
↑ For example,
x = 3 is calculated in 6 steps:
1. 2. 3. 6 561
4. 43 046 721
5. 1 853 020 188 851 841
6. 12 157 665 459 056 928 801