Mathematical induction

Complete induction is a mathematical method of proof according to which a statement is proven for all natural numbers that are greater than or equal to a certain starting value. Since there are an infinite number of numbers involved, a derivation cannot be provided for each number individually.

The proof that the statement $\operatorname {A} (n)$ for all $n\geq n_{0}$ ( $n_{0}$ mostly 1 or 0) holds, is therefore performed in two stages:

In the induction start, the statement $\operatorname {A} (n_{0})$ $n_{0}$ derived for a smallest number .
In the induction step, for any statement A $\operatorname {A} (n)$ the statement $\operatorname {A} (n-1)$ derived.

Or put in less "mathematical" terms:

Induction start: It is proved that the statement holds for the smallest number, the starting value.
Induction step: The following is proven: If the statement is true for any number, it is also true for the number one greater.

Starting from the proof for the initial value, the induction step does the proof for all natural numbers above the initial value.

This proof method is of fundamental importance for arithmetic and set theory and thus for all areas of mathematics.

Statement forms

Complete induction deals with the validity of propositional forms $\operatorname {A} (n)$ .

Example (See Gaussian summation formula):

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

If one inserts values for $n\in \mathbb{N}$ , we obtain statements that are true or false.

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

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

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

$\vdots$

The statements in the above example are obviously all true. Since one cannot recalculate this for all (infinitely many) numbers, it requires a special proof procedure. This is provided by the complete induction.

The propositional form $\operatorname {A} (n)$ is generally valid if it is true for all $n\in \mathbb{N}$ true.

To prove the generality of the propositional form $\operatorname {A} (n)$ show the following:

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

Illustration

The method of complete induction can be compared to the domino effect: If the first domino falls and each falling domino knocks over the next domino, eventually each domino of the infinitely long imaginary chain will fall over at some point.

The generality of a propositional form $\operatorname {A} (n)$ is $n=1,2,3,\ldots$ proved for if $\operatorname {A} (1)$ is valid (the first stone falls over) and if in addition $\operatorname {A} (n)\Rightarrow \operatorname {A} (n+1)$ for $n=1,2,3,\ldots$ (each stone takes the next stone with it when it falls over).

Complete induction as domino effect with infinite stones

Etymology and history

The term induction is derived from Latin inductio, literally "leading to". The addition completely signals that this is a recognized deductive proof procedure in contrast to philosophical induction, which deduces a general law from special cases and is not an exact conclusion procedure.

The principle of induction is already latent in the Pythagorean definition of number handed down by Euclid: "Number is the quantity composed of units." Euclid, however, did not yet carry out induction proofs, but contented himself with intuitive, exemplary inductions, which, however, can be completed. Also other important mathematicians of the antiquity and the Middle Ages had still no need for precise induction proofs. Isolated exceptions in the Hebrew and Arabic language areas remained without succession.

For a long time a proof of Franciscus Maurolicus from 1575 was considered as the oldest explicit complete induction (explained below). However, he did not yet discuss the general method of proof. Only Blaise Pascal addressed the induction principle with induction start and induction step in his Traité du triangle arithmétique of 1654. Jakob I Bernoulli contributed significantly to the spread of induction proofs from 1686.

The proof procedure was then called induction or successive induction for the first time in 1838 by Augustus De Morgan. Finally, in 1888, Richard Dedekind coined the term complete induction in his work What are and what are the numbers? Through this work from the founding period of set theory, it became a generally known, established principle of proof, which since then no branch of mathematics can do without. One year later, in 1889, Giuseppe Peano formulated with Peano's axioms the first formalized calculus for the natural numbers with an induction 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, all arithmetic up to the realnumbers is derivable. Thus he made fully aware the fundamental importance and the power of induction.

Definition

Since Richard Dedekind, complete induction has been defined as follows:

To prove that a theorem holds for all natural numbers $n\ge n_0$ it suffices to show,

that it is valid for $n=n_{0}$ and
that from the validity of the theorem for a number $n\ge n_0$ always follows its validity also for the following number

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

$\operatorname {A} (n_{0})$ and $\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 conclusion rule is a compact formulation of the proof scheme of complete induction, which can be didactically formulated in somewhat more detail:

If the formula $\operatorname {A} (n)$ for all natural numbers $n\ge n_0$ , then two proof steps are sufficient:

1. the induction start: the proof of $\operatorname {A} (n_{0})$ ,

2. the induction step (also called "inference from to n+1 "): the proof of the induction assertion $\operatorname {A} (n+1)$ from $n\ge n_0$ and the induction hypothesis $\operatorname {A} (n)$ .

According to the above rule of inference then follows the generalization of the formula $\operatorname {A} (n)$ to all natural numbers $n\ge n_0$ (the final induction inference).

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

(1)	as induction assertion	for a (single) arbitrary $n\in K$
(2)	as induction prerequisite	for finitely many smaller natural numbers $k\in K$
(3)	as a general statement to be proved	for all (and thus for infinitely many) $n\in K$

Usually n_0=0 or n_0=1 . $n_{0}>1$ However, possible.

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

${\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 the natural numbers by Peano

In 1889 Peano proved by complete induction the basic rules of arithmetic for addition and multiplication: the associative law, commutative law, and distributive law.

The axiom of complete induction

The complete induction is an axiom of the natural numbers. Mostly, however, it is derived from the equivalent fifth Peano axiom, the induction axiom. This reads:

If $\,K$ is a subset of the natural numbers $\mathbb {N}$ with the properties:

$\,1$ is an element of $\,K$
With $\,n$ from $\,K$ is always also $\,n+1$ from $\,K$ ,

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

Also in other concepts of the natural numbers the Peano axioms and thus also the proof procedure of the complete induction are derivable, for example with the definition of the natural numbers

as an ordered semigroup generated by 1, which corresponds to the quoted Pythagorean number definition
as a monoid generated freely from 1, which starts from the addition of the numbers
as algebra with successor mapping corresponding to Dedekind's number definition
as the smallest inductive set, namely as the smallest set that satisfies the axiom of infinity, as it is common in set theory
as a class of finite ordinal numbers, which presupposes only a general set theory without infinity axiom

Examples

Gaussian summation formula

→ Main article: Gaussian summation formula

The Gaussian summation formula is:

For all natural numbers $n \geq 1$ the statement holds
$\operatorname {A} (n):\Longleftrightarrow$	$1+2+\cdots +n$	$={\frac {n(n+1)}{2}}$ .

It can be proved by complete induction.

The induction start results directly:

$\operatorname {A} (1)\Longleftrightarrow$

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

In the induction step, show that for $n \geq 1$ from the induction assumption.

$\operatorname {A} (n)\Longleftrightarrow$

$1+2+\cdots +n$

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

the induction assertion

$\operatorname {A} (n\!+\!1)\Longleftrightarrow$	$1+2+\cdots +(n\!+\!1)$	$={\frac {(n\!+\!1){\bigl (}(n\!+\!1)+1{\bigr )}}{2}}$
		$={\frac {(n+1)(n+2)}{2}}$

(with $(n\!+\!1)$ in the place of the induction condition) follows.

This is accomplished as follows:

${\color {red}1+2+\cdots +n}+(n+1)$	${\color {red}={\frac {n(n+1)}{2}}}+(n+1)$	(red marks the induction condition)
	$={\frac {n(n+1)+2(n+1)}{2}}$	(After factoring out get ...)
$=1+2+\cdots +(n\!+\!1)$	$={\frac {(n+1)(n+2)}{2}}$	(... the induction assertion $\operatorname {A} (n\!+\!1)$ as given above).

Finally, the induction conclusion:
thus the statement $\operatorname {A} (n)$ for all $n\geq 1$ proved.

Sum of odd numbers (Maurolicus 1575)

The stepwise calculation of the sum of the first odd numbers suggests: the sum of all odd numbers from to 2n-1 is equal to the square of :

$1=1$

1+3=4

$1+3+5=9$

$1+3+5+7=16$

The general theorem to be proved is: $\textstyle \sum\limits^n_{i=1} (2i-1) = n^2$ . Maurolicus proved it in 1575 with complete induction. A proof with today's common arithmetic rules reads as follows:

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

As an induction step, show: If $\textstyle \sum\limits^n_{i=1} (2i-1) = n^2$ , then $\textstyle \sum\limits^{n+1}_{i=1} (2i-1) = (n+1)^2$ . It is obtained via the following chain of equations, where the induction condition is applied in the second transformation:

${\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 requirement is marked in red).

Bernoulli's inequality

The Bernoulli inequality is for real numbers $\,x$ with $x\geq -1$ and natural numbers $n \geq 0$

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

The induction start with n=0 holds here because of $(1+x)^0 = 1 \geq 1$ (where the definition gap at the point $\lim _{x\searrow -1}(1+x)^{0}=1$ steadily completed x=-1 by ).

The induction step is obtained via the following derivation, which uses the induction condition in the second step, where the above condition for $\,x$ ensures that the term does not become negative:

${\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 requirement is marked in red).

The two occurrences of the ≥ $\geq$ character (in the same direction) can be simplified to:

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

Horse paradox

→ Main article: Horse paradox

The horse paradox is a standard example of a faulty application of complete induction and illustrates the importance of the interaction of induction anchoring and induction step. In it, the nonsensical statement that in a herd of horses all always have the same color is proved using an apparently correct induction. Here the induction step itself is correct, but would require induction anchoring at an $n\geq 2$ , while the (incorrect) proof anchors the induction at n=1 and already the step from n=1 to n=2 fails.

Play media file Proof of the sum formula over odd numbers using complete induction

Induction variants

Induction with any start

Induction proof of the inequality $2^n\ge n^2$ for natural numbers $n\ge 4$ :

The induction start for $\,n = 4$ given by $2^{4}=16\ge 16 = 4^2$ .

The induction step holds due to the following derivation, which applies the induction condition in the second step and the condition $n\ge 4$ the fourth and sixth steps:

${\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 finitely many cases which such a more general induction proof does not cover can be examined individually. In the example the inequality for n=3 obviously false.

Strong induction

Induction with multiple predecessors

In some induction proofs one does not get along in the induction precondition with the reference to a single predecessor, for example if a recursion formula contains several predecessors. The induction start is to be accomplished then for several starting values. If, for example, the induction precondition for and n-1 derivation of a formula, then an induction start is required for two consecutive numbers, for example 0 and 1. The statement for all numbers between the initial value and can also serve as an induction condition. An example is the proof that every natural number $n\geq 2$ has a prime divisor:

Induction start: 2 is divisible by the prime number 2.

Induction step: Let the statement be true for all with $2\leq m \leq n$ Now if n+1 a prime number, then n+1 itself the divisor we are looking for, and the assertion is proved. If is $\,n+1$ not a prime, then there are two numbers $a,b\in \mathbb {N}$ with $a\cdot b=n+1$ and In this case, according to induction assumption (= induction assumption), a prime divisor, say . Then also divides n+1 and is prime divisor of n+1 . Thus the assertion is proved also for this second case.

Formal definition

The statement $\operatorname {A} (n)$ is $n\ge n_0$ valid for all following is $n\ge n_0$ shown for any

(Induction step:)

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

Accordingly, the proof scheme of strong induction consists only of the induction step.

The induction step is therefore the proof that
	for each $n\ge n_0$
	the induction condition
	the induction assertion	$\operatorname {A} (n)$ entails.
Then follows the generalization
	(the induction closure):	The statement $\operatorname {A} (n)$ holds for all $n\ge n_0$ .

Induction beginnings as they occur in ordinary induction, e.g. the proof of the statement $\operatorname {A} (n_{0})$ , are included in the induction step. Moreover, it may 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:

If for all $n\ge n_0$

	from $\bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)$	$\left.{\begin{matrix}\\\\\\\\\end{matrix}}\right\rbrace$	(Induction condition usually ⇒ strong)
	$\operatorname {A} (n)$ follows,	$\left.{\begin{matrix}\\\\\\\\\end{matrix}}\right\rbrace$	(Induction condition usually ⇒ strong)

then applies

$\operatorname {A} (n)$ for all $n\geq n_{0}$ .

(induction closure usually ⇒ strong)

We define the following statement $\operatorname {B}$ for natural numbers $n\in \mathbb {N} ,n\geq n_{0}$

$\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 $\operatorname {B} (n_{0})\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n_{0}-1}\operatorname {A} (m)\Longleftrightarrow \bigwedge _{m\in \emptyset }\operatorname {A} (m)$ , which is empty ampersand, $\operatorname {B} (n_{0})$ according to Remark immediately.

(Ordinary) induction step from to n+1 :

Let be $n\ge n_0$ arbitrary and let $\operatorname {B} (n)$ , i.e. it holds

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

Because of the (induction assumption usually ⇒ strong) it follows that

$\operatorname {A} (n)$ .

Taken together with $\textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)$ gives this

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

Thus we have $\operatorname {B} (n+1)$ which $\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n}\operatorname {A} (m)$ , and the ordinary induction step is done. We conclude (ordinary induction closure):

For all $n\in \mathbb {N} ,n\geq n_{0}$ holds $\operatorname {B} (n)$ .

Because $\operatorname {B} (n)\Longleftrightarrow \textstyle \bigwedge _{m=n_{0}}^{n-1}\operatorname {A} (m)$ yields a fortiori the strong induction inference:

For all $n\in \mathbb {N} ,n\geq n_{0}$ holds $\operatorname {A} (n)$ . ■

Despite this equivalence in principle in the strength of proof, the difference in expressive strength is large because of the arbitrarily many initial values and the possibility of recourse to arbitrarily many predecessors, especially for recursive definitions. However, this does not at all mean that the latter definitions cannot be transformed into ordinary recursions.

Example

Let the sequence $\left(a_{n}\right)_{{n\in \mathbb{N} }}$ be defined by the recursion formula $a_{n}:=\sum _{m=1}^{n-1}ma_{m}$ .
Then $\forall n\in \mathbb {N} \colon a_{n}=0$ .
The proof by strong induction is trivial.
However, the recursion can also be easily transformed into one on a single antecedent:
$a_{n}=\sum _{m=1}^{n-2}ma_{m}+(n-1)\,a_{n-1}={\bigl (}1+(n-1){\bigr )}\,a_{n-1}$
$(n\geq 2)$ .

Induction with forward-backward steps

In 1821, Augustin-Louis Cauchy introduced an induction variant in which the forward induction step makes jumps (namely, from $2^{k}$ to $2^{k+1}$ ) and the resulting gaps are subsequently $n<2^{k}$ filled in one fell swoop by a backward induction from $2^{k}$ to

Example: Inequality of arithmetic and geometric mean

Other induction variants

There are also situations where statements about all integers (positive and negative) can be proved with complete induction. The proof in the positive direction is done as usual with any induction start and the positive induction step from to n+1 . Thereafter, it may be possible to n-1 perform the induction step in the negative direction from to For example, in the Fibonacci sequence, the recursion equation can be inverted in the opposite direction.

The complete induction is generalizable from natural numbers to ordinal numbers. For ordinal numbers, which are larger than the natural numbers, one speaks then of transfinite induction.

The induction is also transferable to so-called well-founded sets, which have an order structure comparable to the number order; here one sometimes speaks 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

$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 the complete induction one can prove (Gaussian sum formula):

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

The closed formula saves the cumbersome recursive calculation.

Conversely, the next example shows that a recursive calculation can be more convenient.

Example of a recursively defined function:

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

One can show by complete induction on that

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

The advantage of this recursive definition is that when computing high powers, one does not $\ln(n)$ have multiplications, but only multiplications in the order of Very high powers are used, for example, in RSA message encryption.

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

Questions and Answers

Q: What is mathematical induction?

A: Mathematical induction is a special way of proving a mathematical truth that can be used to prove something is true for all natural numbers or positive numbers from a certain point onwards.

Q: How does the proof by induction proceed?

A: The proof by induction typically proceeds by stating that the proof will be done over n, showing that the statement is true when n is 1, assuming that the statement is true for any natural number n, and then showing it's true for the next number (n+1).

Q: What does it mean to assume something in an inductive step?

A: To assume something in an inductive step means to accept it as being true without providing evidence or proof. It serves as a starting point for further investigation.

Q: What kind of numbers are used in mathematical induction?

A: Mathematical induction typically uses natural numbers or positive numbers from a certain point onwards.

Q: How do you show that something is true for the next number (n+1)?

A: To show that something is true for the next number (n+1), you must first prove it's true when n=1, and then use your assumption from the inductive step to show it's also true for n+1.