MATHESIS :: Essential
< All Topics

Reasoning by induction

Posted
Updated
ByM4t_6_onL

The argument by induction is perhaps the most emblematic of mathematical science and the one that fascinates and disconcerts the most.

It is used when one seeks to prove a property P (which depends) on the natural numbers, in other words a statement of the form “\forall n\in \mathbb N, P(n)“.

Such a statement often covers many other relationships between related objects other than the natural numbers, implicit in the formula P(n).

Reasoning by induction consists in proving P(0), i.e. the property P for the value n=0 (which is called the induction start), and assuming that P(n) is true (which is called the induction hypothesis), in proving that P(n+1) is true: this is called the induction step. From “close to close”, this leads to the fact that P(n) is true for any natural number n.

We reason in this way because the set \mathbb N being infinite, it is not possible to prove the property P(n) for all the natural numbers n individually, i.e. P(0), P(1), P(2), … .

Example 1
The clause P(n) : “\forall x\in\mathbb R_+,\forall y\in \mathbb R_+,\ x\leq y\Rightarrow x^n\leq y^n“, where n denotes a generic natural number, is a property of n which mentions generic real numbers.

  • The property P(0) is “\forall x\in\mathbb R_+,\forall y\in \mathbb R_+,\ x\leq y\Rightarrow 1\leq 1“, since x^0=1 for any real number x
  • The induction step consists in proving P(n+1), i.e. “\forall x\in\mathbb R_+,\forall y\in \mathbb R_+,\ x\leq y\Rightarrow x^{n+1}\leq y^{n+1}“, by assuming P(n). \square

Intuitively, we can compare reasoning by induction to a game of dominoes: we have to make the first domino fall, then each time a domino falls, it drags in its fall the following domino and, step by step, all the dominoes fall.

Similarly, you have to prove the property for the first natural number, and then from one step to the next, each time it is proved for one natural number, it will be true for the next number, if at least you can show the transition from one step to the next, which is often the effort involved in the demonstration.

What makes this possible is that one does not demonstrate each step of the induction individually, but “generically”.

Example 2
Using the same example, let us prove by induction on n that for all n\in\mathbb N, P(n) is true. Let x,y be two positive real numbers:

  1. Induction start: If n=0, then a^n=a^0=1=b^0=b^n by convention, so the inequality holds for n=0
  2. Induction hypothesis: Suppose that P(n) is true for a natural number n, i.e. that a^n=a^0=1=b^0=b^n
  3. Induction step: We then have a^{n+1}=a^n.a (by definition) \leq a^n.b (because a\leq b and b^n\geq 0) \leq b^n.b (by applying the induction hypothesis and multiplication by b\geq 0) =b^{n+1}
  4. The property is verified at rank n+1, so we have proved by induction that it is verified for all n\in\mathbb N. \square

The justification of this type of argument is based on the induction principle. Indeed, to show that the property P(n) is true for any natural number n is to prove that the set S of natural numbers for which P(n) is true (symbolically S=\{n\in\mathbb N : P(n)\}), is the set whole set \mathbb N.

For that, one applies the induction principle (REF): one must show that 0\in S (in other words that the property P(0) is true, initial step), then that n+1\in S as soon as n\in S (in other words, that P(n+1) is true as soon as P(n) is true, induction step). The principle of demonstration by induction is thus a reformulation of the induction principle!

Table of Contents