Induction complète en mathématiques

L’Induction Complète : Définition et Exemples

L’induction complète, également appelée induction mathématique ou raisonnement par induction, est une méthode de démonstration utilisée principalement en mathématiques et en logique pour établir qu’une propriété ou une relation est vraie pour tous les éléments d’un ensemble infini. Elle repose sur une technique en deux étapes : d’abord, on prouve que la propriété est vraie pour un élément de base (souvent l’élément initial d’une suite ou d’un ensemble), puis on montre que si elle est vraie pour un certain élément, elle est également vraie pour l’élément suivant. Cette méthode est utilisée pour prouver des théorèmes concernant des suites, des séries, des nombres, ou encore des objets mathématiques bien définis.

Les Étapes de l’Induction Complète

L’induction complète se décompose généralement en trois étapes fondamentales :

1. Vérification du cas de base (initialisation) : Il s’agit de démontrer que la propriété à prouver est vraie pour un premier élément de l’ensemble considéré. Ce cas est souvent un cas particulier, par exemple $n = 0$ ou $n = 1$, selon la structure de l’énoncé.

2. Hypothèse d’induction : On suppose que la propriété est vraie pour un certain entier $k$, généralement noté « hypothèse d’induction ». Cette étape n’est pas une preuve en soi, mais une supposition que l’on utilise pour construire la démonstration pour l’élément suivant.

3. Induction : On montre que, sous l’hypothèse que la propriété est vraie pour $k$, elle est aussi vraie pour $k + 1$. C’est cette étape qui permet de « propager » la vérité de la propriété pour un élément à tous les éléments suivants de la suite.

Si ces trois étapes sont remplies, on peut conclure que la propriété est vraie pour tous les éléments de l’ensemble.

Exemple 1 : La Somme des $n$ Premiers Entiers

Prenons l’exemple classique de la somme des premiers $n$ entiers naturels, c’est-à-dire la somme de $1 + 2 + 3 + \dots + n$. La formule pour cette somme est donnée par :

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

Étape 1 : Cas de base

Pour $n = 1$, la somme des entiers est simplement $S_1 = 1$. La formule nous donne également :

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

Le cas de base est donc vérifié.

Étape 2 : Hypothèse d’induction

Supposons que la formule soit vraie pour un entier $k$, c’est-à-dire :

$$S_k = \frac{k(k+1)}{2}$$

Étape 3 : Induction

Nous devons maintenant montrer que la formule est vraie pour $k+1$, c’est-à-dire que :

$$S_{k+1} = 1 + 2 + 3 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}$$

En utilisant l’hypothèse d’induction, on peut écrire $S_{k+1}$ comme :

$$S_{k+1} = S_k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

Factorisons $(k+1)$ :

$$S_{k+1} = (k+1)\left( \frac{k}{2} + 1 \right) = (k+1)\left( \frac{k+2}{2} \right) = \frac{(k+1)(k+2)}{2}$$

Cela montre que la formule est vraie pour $k+1$. Par le principe d’induction, la formule est donc vraie pour tous les entiers naturels $n$.

Exemple 2 : Divisibilité par 2

Prenons l’exemple de l’énoncé suivant : « Tout nombre entier pair peut être écrit sous la forme $2k$, où $k$ est un entier. »

Étape 1 : Cas de base

Pour $n = 0$, nous avons $2 \times 0 = 0$, qui est un nombre pair. Le cas de base est donc vérifié.

Étape 2 : Hypothèse d’induction

Supposons que l’énoncé soit vrai pour un entier $k$, c’est-à-dire que $2k$ est un nombre pair. Nous devons maintenant prouver que $2(k+1)$ est également un nombre pair.

Étape 3 : Induction

Nous avons :

$$2(k+1) = 2k + 2$$

Or, $2k$ est pair d’après l’hypothèse d’induction, et $2$ est évidemment pair. La somme de deux nombres pairs est toujours paire, donc $2(k+1)$ est aussi un nombre pair.

Ainsi, par induction, tout nombre de la forme $2k$ est pair.

Exemple 3 : Formule de la Factorielle

La factorielle d’un entier $n$, notée $n!$, est le produit des entiers de $1$ à $n$. Par définition, on a :

$$n! = 1 \times 2 \times 3 \times \dots \times n$$

Nous voulons prouver, par induction, que pour tout entier $n \geq 1$, la relation $n!$ est divisible par $n$.

Étape 1 : Cas de base

Pour $n = 1$, $1! = 1$, qui est divisible par 1. Le cas de base est vérifié.

Étape 2 : Hypothèse d’induction

Supposons que la propriété soit vraie pour un entier $k$, c’est-à-dire que $k!$ est divisible par $k$.

Étape 3 : Induction

Nous devons maintenant prouver que $(k+1)!$ est divisible par $k+1$. On a :

$$(k+1)! = (k+1) \times k!$$

Par hypothèse d’induction, $k!$ est divisible par $k$. Or, $(k+1)$ est un facteur supplémentaire, ce qui implique que $(k+1)!$ est également divisible par $k+1$. Cela conclut la démonstration.

Conclusion

L’induction complète est une technique puissante et élégante pour prouver des propositions sur des ensembles infinis ou des suites. En utilisant une base solide et une propagation par étapes successives, elle permet de démontrer des résultats fondamentaux en mathématiques, en logique et dans d’autres domaines scientifiques. Les exemples ci-dessus illustrent bien la méthode, qui repose sur des principes simples mais robustes. Que ce soit pour la somme des entiers, la divisibilité, ou encore la factorielle, l’induction complète est un outil incontournable dans le répertoire du mathématicien.