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: ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle n_{0}}$

1. In the beginning of induction , the statement is derived for a smallest number . ${\displaystyle \operatorname {A} (n_{0})}$ ${\displaystyle n_{0}}$
2. In the induction step is for any the statement from the statement derived. ${\displaystyle n>n_{0}}$ ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle \operatorname {A} (n-1)}$

Or to put it less "mathematically":

1. Induction start : It is proven that the statement applies to the smallest number, the starting value.
2. 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 . ${\displaystyle \operatorname {A} (n)}$

Example (see Gaussian empirical formula ):

${\displaystyle \operatorname {A} (n):1+2+3+\dots +n={\tfrac {n\cdot (n+1)}{2}}}$ For ${\displaystyle n\geq 1}$

If you substitute values ​​for , you get statements that are true or false. ${\displaystyle n\in \mathbb {N} }$

${\displaystyle \operatorname {A} (1):1={\tfrac {1\cdot (1+1)}{2}}}$

${\displaystyle \operatorname {A} (2):1+2={\tfrac {2\cdot (2+1)}{2}}}$

${\displaystyle \operatorname {A} (3):1+2+3={\tfrac {3\cdot (3+1)}{2}}}$

${\displaystyle \vdots }$

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 . ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\in \mathbb {N} }$

To prove the general validity of the statement form, one shows the following: ${\displaystyle \operatorname {A} (n)}$

1. ${\displaystyle \operatorname {A} (1)}$ (Start of induction) and
2. the statement always follows from the statement (the induction assumption) , and that for all . (This is the induction step.) ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle \operatorname {A} (n+1)}$ ${\displaystyle n\in \mathbb {N} }$

illustration

Complete induction as a domino effect with an infinite number of stones

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 ). ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n=1,2,3,\ldots }$ ${\displaystyle \operatorname {A} (1)}$ ${\displaystyle \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1)}$ ${\displaystyle n=1,2,3,\ldots }$

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 ${\displaystyle n\geq n_{0}}$

• that it applies to and ${\displaystyle n=n_{0}}$
• that the validity of the proposition for a number always implies its validity for the following number . ${\displaystyle n\geq n_{0}}$ ${\displaystyle n+1}$

As a formal rule of inference with a derivative operator , the complete induction for a statement and a natural number reads : ${\displaystyle \vdash }$ ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n_{0}}$

${\displaystyle \operatorname {A} (n_{0})}$ and ${\displaystyle \forall n\in \mathbb {N} \colon (n\geq n_{0}\land \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1))\ \vdash \ \forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n))}$

---

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 sufficient ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq n_{0}}$proofsteps:

1. the beginning of induction : theproofof , ${\displaystyle \operatorname {A} (n_{0})}$
2. the induction step (also "Enough of on " called): the ${\displaystyle n}$ ${\displaystyle n+1}$proofthe inductive claim from and the induction hypothesis (also induction hypothesis , engl. induction hypothesis ) . ${\displaystyle \operatorname {A} (n+1)}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle \operatorname {A} (n)}$

According to the above rule of inference, the generalization of the formula to all natural numbers follows (the final induction conclusion ). ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq n_{0}}$

The statement to be proven for natural numbers from a set occurs in at least 3 roles : ${\displaystyle k\in K}$ ${\displaystyle K\subseteq \mathbb {N} }$ ${\displaystyle \operatorname {A} (k)}$

(1)	as an induction claim		for any (single) ${\displaystyle n\in K}$
(2)	as an induction requirement		for finitely many smaller natural numbers ${\displaystyle k\in K}$
(3)	as a general statement to be proven		for everyone (and thus for an infinite number) ${\displaystyle n\in K}$

---

Usually is or . however, it is possible. ${\displaystyle n_{0}=0}$ ${\displaystyle n_{0}=1}$ ${\displaystyle n_{0}>1}$

Because the statement for is equivalent to the statement for , Dedekind's induction can be reduced to the complete induction from 0: ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle B(n):=A(n+n_{0})}$ ${\displaystyle n\geq 0}$

${\displaystyle {\begin{array}{llll}\operatorname {B} (0){,}&&&\forall n\in \mathbb {N} \colon (\operatorname {B} (n)&\Rightarrow \operatorname {B} (n+1))\ &&&\vdash \ \forall n\in \mathbb {N} \colon &\operatorname {B} (n)\\\Uparrow &&&&\Uparrow &&&&\Downarrow \\\operatorname {A} (0+n_{0}){,}&&&\forall n\in \mathbb {N} \colon (\operatorname {A} (n+n_{0})&\Rightarrow \operatorname {A} (n+1+n_{0}))\ &&&&\operatorname {A} (n+n_{0})\end{array}}}$

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: ${\displaystyle \,K}$ ${\displaystyle \mathbb {N} }$

1. ${\displaystyle \,1}$ is an element of ${\displaystyle \,K}$
2. With off is always off , ${\displaystyle \,n}$ ${\displaystyle \,K}$ ${\displaystyle \,n+1}$ ${\displaystyle \,K}$

then is . ${\displaystyle \,K=\mathbb {N} }$

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

→ Main article : Gaussian empirical formula

The Gaussian empirical formula reads: The following applies to all natural numbers ${\displaystyle n\geq 1}$

${\displaystyle \operatorname {A} (n):}$

${\displaystyle 1+2+\cdots +n={\frac {n(n+1)}{2}}}$

It can be proven by complete induction.

The induction start results immediately:

${\displaystyle \operatorname {A} (1):}$

${\displaystyle 1={\frac {1(1+1)}{2}}}$.

In the induction step it has to be shown that from the induction hypothesis

${\displaystyle \operatorname {A} (n):}$

${\displaystyle 1+2+\cdots +n={\frac {n(n+1)}{2}}}$

the induction claim

${\displaystyle \operatorname {A} (n+1):}$

${\displaystyle 1+2+\cdots +n+(n+1)={\frac {(n+1)(n+2)}{2}}}$ For ${\displaystyle n\geq 1}$

follows. This is achieved as follows:

${\displaystyle {\color {red}1+2+\cdots +n}+(n+1)}$	${\displaystyle {\color {red}={\frac {n(n+1)}{2}}}+(n+1)}$
	${\displaystyle ={\frac {n(n+1)+2(n+1)}{2}}}$	(Main denominator 2)
	${\displaystyle ={\frac {(n+1)(n+2)}{2}}}$	(Exclude from ) ${\displaystyle (n+1)}$
	${\displaystyle ={\frac {(n+1){\bigl (}(n+1)+1{\bigr )}}{2}}}$	(with in the place of ) ${\displaystyle (n+1)}$ ${\displaystyle n}$

(The induction hypothesis is marked in red.)

Finally the induction conclusion: This proves the statement for everyone . ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq 1}$

Sum of odd numbers (Maurolicus 1575)

Play media file

Proof of the empirical formula over odd numbers with the help of complete induction

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 : ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle 2n-1}$ ${\displaystyle n}$

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: ${\displaystyle \textstyle \sum \limits _{i=1}^{n}(2i-1)=n^{2}}$

The beginning of induction with is easily checked because of . ${\displaystyle \textstyle \sum \limits _{i=1}^{1}(2i-1)=1^{2}}$ ${\displaystyle n=1}$ ${\displaystyle \textstyle \sum \limits _{i=1}^{1}(2i-1)=2\cdot 1-1=1=1^{2}}$

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: ${\displaystyle \textstyle \sum \limits _{i=1}^{n}(2i-1)=n^{2}}$ ${\displaystyle \textstyle \sum \limits _{i=1}^{n+1}(2i-1)=(n+1)^{2}}$

${\displaystyle {\begin{aligned}\sum _{i=1}^{n+1}(2i-1)\;&=\;\;{\color {red}\sum _{i=1}^{n}(2i-1)}+(2(n+1)-1)\\&\ {\color {red}=\;\;\ n^{2}}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}\end{aligned}}}$

(The induction hypothesis is marked in red.)

Bernoulli's inequality

The Bernoulli's inequality is for real numbers with and natural numbers ${\displaystyle \,x}$ ${\displaystyle x\geq -1}$ ${\displaystyle n\geq 0}$

${\displaystyle (1+x)^{n}\geq 1+nx}$.

The induction start with applies here because of (whereby the definition gap at this point is supplemented by continuously ). ${\displaystyle n=0}$ ${\displaystyle (1+x)^{0}=1\geq 1}$ ${\displaystyle x=-1}$ ${\displaystyle \lim _{x\searrow -1}(1+x)^{0}=1}$

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: ${\displaystyle \,x}$

${\displaystyle {\begin{aligned}(1+x)^{n+1}&={\color {red}(1+x)^{n}}\cdot (1+x)\,\,{\color {red}\geq \;(1+nx)}\cdot (1+x)\\&=1+x+nx+nx^{2}\;\geq \;1+x+nx\\&=1+(n+1)x.\end{aligned}}}$

(The induction hypothesis is marked in red.)

The two occurrences of the -sign (in the same direction) can be simplified to: ${\displaystyle \geq }$

${\displaystyle (1+x)^{n+1}\geq 1+(n+1)x.}$

Equine paradox

→ Main article : Horse 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. ${\displaystyle n}$ ${\displaystyle n\geq 2}$ ${\displaystyle n=1}$ ${\displaystyle n=1}$ ${\displaystyle n=2}$

Induction variants

Induction with any beginning

Induction proof of the inequality for natural numbers : ${\displaystyle 2^{n}\geq n^{2}}$ ${\displaystyle n\geq 4}$

The induction start for results from . ${\displaystyle \,n=4}$ ${\displaystyle 2^{4}=16\geq 16=4^{2}}$

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 : ${\displaystyle n\geq 4}$

${\displaystyle {\begin{array}{lll}2^{n+1}&=2\cdot 2^{n}\geq 2\cdot n^{2}&=n^{2}+n\cdot n\geq n^{2}+4n\\&=n^{2}+2n+2n&\geq n^{2}+2n+2\cdot 4\\&\geq n^{2}+2n+1&=(n+1)^{2}.\end{array}}}$

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. ${\displaystyle n=3}$

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: ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n\geq 2}$

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. ${\displaystyle m}$ ${\displaystyle 2\leq m\leq n}$ ${\displaystyle n+1}$ ${\displaystyle n+1}$ ${\displaystyle \,n+1}$ ${\displaystyle a,b\in \mathbb {N} }$ ${\displaystyle a\cdot b=n+1}$ ${\displaystyle 1<a<n+1}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n+1}$ ${\displaystyle n+1}$

Formal definition

The statement is valid for all if the following is shown for any : ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle n\geq n_{0}}$

(Induction step :)

${\displaystyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)\implies \operatorname {A} (n)}$ .

The proof scheme of strong induction accordingly consists only of the induction step .

The induction step is therefore the proof that
	for each ${\displaystyle n\geq n_{0}}$
	the induction hypothesis	${\displaystyle \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}$
	the induction claim	${\displaystyle \operatorname {A} (n)}$   entails.
Then the generalization follows
	(the induction closure):	The statement applies to everyone . ${\displaystyle \operatorname {A} (n)}$ ${\displaystyle n\geq n_{0}}$

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 ). ${\displaystyle \operatorname {A} (n_{0})}$

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: If for everyone ${\displaystyle n\geq n_{0}}$ out ${\displaystyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}$ ${\displaystyle \left.{\begin{matrix}\\\\\\\\\end{matrix}}\right\rbrace }$ (Induction assumption usually ⇒ strong) ${\displaystyle \operatorname {A} (n)}$ follows, then applies ${\displaystyle \operatorname {A} (n)}$ For all ${\displaystyle n\geq n_{0}}$. (Induction closure usually ⇒ strong) We define the following statement for natural numbers ${\displaystyle \operatorname {B} }$ ${\displaystyle n\in \mathbb {N} ,n\geq n_{0}}$ ${\displaystyle \operatorname {B} (n):\Longleftrightarrow \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}$ 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. ${\displaystyle \operatorname {B} (n_{0})\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n_{0}-1}\operatorname {A} (m)\Longleftrightarrow \bigwedge _{m\in \emptyset }\operatorname {A} (m)}$ ${\displaystyle \operatorname {B} (n_{0})}$ (Ordinary) induction step from to : ${\displaystyle n}$ ${\displaystyle n+1}$ Be arbitrary and let it be , d. H. it applies ${\displaystyle n\geq n_{0}}$ ${\displaystyle \operatorname {B} (n)}$ ${\displaystyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}$. Because of the (induction assumption usually ⇒ strong) it follows ${\displaystyle \operatorname {A} (n)}$. Taken together with this gives ${\displaystyle \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}$ ${\displaystyle \bigwedge _{m=n_{0}}^{n}\operatorname {A} (m)}$. With that we have shown which one is, and the usual induction step is done. We conclude (ordinary induction closure): ${\displaystyle \operatorname {B} (n+1)}$ ${\displaystyle \Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n}\operatorname {A} (m)}$ For all ${\displaystyle n\in \mathbb {N} ,n\geq n_{0}}$applies . ${\displaystyle \operatorname {B} (n)}$ Because of this, the strong induction conclusion arises a fortiori : ${\displaystyle \operatorname {B} (n)\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)}$ For all ${\displaystyle n\in \mathbb {N} ,n\geq n_{0}}$applies . ■ ${\displaystyle \operatorname {A} (n)}$

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 . ${\displaystyle \left(a_{n}\right)_{n\in \mathbb {N} }}$
        ${\displaystyle a_{n}:=\sum _{m=1}^{n-1}ma_{m}}$
  
        ${\displaystyle \forall n\in \mathbb {N} \colon a_{n}=0}$
  
  
        ${\displaystyle a_{n}=\sum _{m=1}^{n-2}ma_{m}+(n-1)\,a_{n-1}={\bigl (}1+(n-1){\bigr )}\,a_{n-1}}$       ${\displaystyle (n\geq 2)}$

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 . ${\displaystyle 2^{k}}$ ${\displaystyle 2^{k+1}}$ ${\displaystyle 2^{k}}$ ${\displaystyle n<2^{k}}$

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 . ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n-1}$

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

${\displaystyle f(n)={\begin{cases}1&&\mathrm {f{\ddot {u}}r} \ n=1\\n+f(n-1)&&\mathrm {f{\ddot {u}}r} \ n>1\\\end{cases}}}$

With the help of complete induction one can prove ( Gaussian sum formula ):

${\displaystyle f(n)={\frac {n(n+1)}{2}}}$

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:

${\displaystyle f(x,n)={\begin{cases}\\\\\\\\\end{cases}}}$	${\displaystyle 1}$		for   , ${\displaystyle n=0}$
	${\displaystyle x\cdot f(x,n-1)}$		for   and odd, ${\displaystyle n\geq 1}$ ${\displaystyle n}$
	${\displaystyle f\left(x^{2},{\tfrac {n}{2}}\right)}$		for   and straight. ${\displaystyle n\geq 2}$ ${\displaystyle n}$

With the help of complete induction it can be shown that ${\displaystyle n}$

${\displaystyle f(x,n)=x^{n}}$     for is. ${\displaystyle n\geq 0}$

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. ${\displaystyle n}$ ${\displaystyle \ln(n)}$

The recursive definition, like induction, has all kinds of differentiated variants.

Web links

Wikibooks: Math for Non-Freaks: Full Induction  - Study and Teaching Materials

• 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:
  • Sum of odd numbers (Maurolic theorem) on YouTube .
  • Gaussian empirical formula on YouTube .
  • Bernoulli's inequality on YouTube .
  • Proof of 2 ⁿ ≥n ² on YouTube .

Individual evidence

1. ↑ Induction start and induction step can often be derived using methods of "school logic". However, full induction is a second order predicate logic method .
2. ↑ ^{a b} Euclid's Elements VII, Definition 2. In addition: Wilfried Neumaier: Antike Rhythmustheorien , chap. 1 Ancient Mathematical Concepts , pp. 11–12.
3. ^ Rabinovitch: Rabbi Levi Ben Gershon and the Origins of Mathematical Induction , in: Archive for History of Exact Sciences 6 (1970), pp. 237-248.
4. ↑ Roshdi Rashed : L'induction mathématique: al-Karajī, as-Samaw'al , in: Archive for History of Exact Sciences 9 (1972), pp. 1–21.
5. ↑ ^{a b} Maurolycus: Arithemticorum Liber primus , p. 7, Proposition 15 ^a . limited preview in Google Book search.
6. ↑ 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.
7. ^ Lexicon of important mathematicians, Leipzig 1990, article "Jakob Bernoulli", p. 48.
8. ↑ De Morgan: Article Induction (Mathematics) in: Penny Cyclopædia XII (1838), pp. 465-466.
9. ↑ ^{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 ₀ , 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 ₀ its validity also for the following number n 'follows.
10. ^ Peano: Arithmetices principia nova methodo exposita , 1889, in: G. Peano, Opere scelte II, Rome 1958, pp. 20–55.
11. ^ Peano: Arithmetices principia nova methodo exposita. 1889. In: G. Peano: Opere scelte. Volume II. Rome 1958. pp. 35-36, 40-41.
12. ↑ detailed evidence also in: Edmund Landau : Fundamentals of Analysis. Leipzig 1930.
13. ↑ Felscher: Naive sets and abstract numbers I, pp. 130–132.
14. ↑ Dedekind: What are and what are the numbers? , § 6, declaration 71.
15. ↑ represented as Dedekind triples in: Felscher: Naive Mengen und Abstract Numbers I, p. 147.
16. ^ S. Proof of Binet's formula for the Fibonacci sequence
17. ↑ Another example is the proof of the Zeckendorf theorem ; s. Zeckendorf's theorem .
18. ↑ Is by definition . The induction hypothesis (the induction hypothesis), then, is that for all the numbers from to is assumed to be valid. ${\displaystyle \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)\;=\;\operatorname {A} (n_{0})\wedge \operatorname {A} (n_{0}+1)\wedge \dotso \wedge \operatorname {A} (n-1)}$
    ${\displaystyle \operatorname {A} (m)}$ ${\displaystyle m}$ ${\displaystyle n_{0}}$ ${\displaystyle n-1}$
19. ↑ ^{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. ${\displaystyle {\mathsf {WAHR}}}$ ${\displaystyle \textstyle \bigwedge _{m\in \emptyset }\operatorname {A} (m)}$ ${\displaystyle {\mathsf {WAHR}}}$ ${\displaystyle {\bigl (}{\mathsf {WAHR}}\implies \operatorname {A} (n_{0}){\bigr )}}$ ${\displaystyle \operatorname {A} (n_{0})}$
20. ↑ 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.
21. ↑ Cauchy, Augustin-Louis. Analysis algebrique. Paris 1821. The proof of the inequality of the arithmetic and geometric mean is there on page 457 ff.
22. ↑ 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.
23. ^ Hausdorff: Fundamentals of set theory. 1914. pp. 112–113 limited preview in Google book search.
24. ^ Peano: Le Definitions in Matematica. In: Opere scelte. Volume II, 1921. p. 431, § 7 Definizioni per induione.
25. ↑ 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 ${\displaystyle f(x,40)}$ ${\displaystyle =f(x^{2},20)}$ ${\displaystyle =f(x^{4},10)}$ ${\displaystyle =f(x^{8},5)}$ ${\displaystyle =x^{8}\cdot f(x^{8},4)}$ ${\displaystyle =x^{8}\cdot f(x^{16},2)}$ ${\displaystyle =x^{8}\cdot f(x^{32},1)}$ ${\displaystyle =x^{8}\cdot x^{32}}$ ${\displaystyle =x^{40}}$
    ${\displaystyle x^{40}}$
    ${\displaystyle x^{2}=3\cdot 3=9}$
    ${\displaystyle x^{4}=9\cdot 9=81}$
    ${\displaystyle x^{8}=81\cdot 81=}$
    ${\displaystyle x^{16}=6561\cdot 6561=}$
    ${\displaystyle x^{32}=43046721\cdot 43046721=}$
    ${\displaystyle x^{40}=6561\cdot 1853020188851841=}$

This version was added to the list of articles worth reading on July 15, 2010 .