Reasoning by induction
MATHESIS - Integrating mathematical knowledge in a unique transversal curriculum (logic, arithmetic, algebra, analysis, geometry...)
E-BOOKS - Discover the e-books of the MATHESIS curriculum and master higher mathematics by yourself
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 (which depends) on the natural numbers, in other words a statement of the form ““.
Such a statement often covers many other relationships between related objects other than the natural numbers, implicit in the formula .
Reasoning by induction consists in proving , i.e. the property for the value (which is called the induction start), and assuming that is true (which is called the induction hypothesis), in proving that is true: this is called the induction step. From “close to close”, this leads to the fact that is true for any natural number .
We reason in this way because the set being infinite, it is not possible to prove the property for all the natural numbers individually, i.e. , , , … .
The clause : ““, where denotes a generic natural number, is a property of which mentions generic real numbers.
- The property is ““, since for any real number
- The induction step consists in proving , i.e. ““, by assuming .
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”.
Using the same example, let us prove by induction on that for all , is true. Let be two positive real numbers:
- Induction start: If , then by convention, so the inequality holds for
- Induction hypothesis: Suppose that is true for a natural number , i.e. that
- Induction step: We then have (by definition) (because and ) (by applying the induction hypothesis and multiplication by )
- The property is verified at rank , so we have proved by induction that it is verified for all .
The justification of this type of argument is based on the induction principle. Indeed, to show that the property is true for any natural number is to prove that the set of natural numbers for which is true (symbolically ), is the set whole set .
For that, one applies the induction principle (REF): one must show that (in other words that the property is true, initial step), then that as soon as (in other words, that is true as soon as is true, induction step). The principle of demonstration by induction is thus a reformulation of the induction principle!