Induction
L'induction est une méthode pour démontrer des énoncés qui valent pour tous les nombres naturels.
L'idée est de montrer que si un énoncé vaut pour le premier nombre, et s'il vaut pour un nombre arbitraire \( \large k \), alors il doit aussi valoir pour \( \large k+1 \). De cette manière, on montre que l'énoncé est vrai pour tout \( \large n \).
L'induction fonctionne comme une rangée de dominos : Si la première pièce tombe (le cas de base), et que chaque pièce fait tomber la suivante (le pas inductif), alors toutes les pièces de la rangée tombent.
Démarche
Une démonstration par induction se compose généralement de trois étapes :
1. Base : Montrer que l'énoncé vaut pour le premier nombre naturel, typiquement \( \large n=1 \).
2. Hypothèse d'induction : Supposer que l'énoncé vaut pour un \( \large n=k \) arbitraire.
3. Pas inductif : Utiliser l'hypothèse pour montrer que l'énoncé vaut aussi pour \( \large n=k+1 \).
Exemple 1
Nous voulons démontrer par induction que la somme des \( \large n \) premiers nombres naturels est
$$ \large 1 + 2 + \cdots + n = \frac{n(n+1)}{2} $$
Base :
Pour \( \large n=1 \) on obtient \( \large 1 = \frac{1 \cdot (1+1)}{2} = 1 \). L'énoncé est vrai.
Hypothèse d'induction :
Supposons que l'énoncé vaille pour \( \large n=k \) :
$$ \large 1 + 2 + \cdots + k = \frac{k(k+1)}{2} $$
Pas inductif :
Pour \( \large n=k+1 \) on obtient :
$$ \large 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) $$
$$ \large = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} $$
Ce qui est la même formule avec \( \large n=k+1 \). Ainsi l'énoncé est démontré pour tout \( \large n \).
Exemple 2
Nous voulons démontrer par induction que \( \large 5^n - 2^n \) est toujours divisible par 3 pour tout \( \large n \in \mathbb{N} \).
Base :
Pour \( \large n=1 \) on obtient \( \large 5^1 - 2^1 = 3 \), qui est divisible par 3.
Hypothèse d'induction :
Supposons que l'énoncé vaille pour \( \large n=k \) :
$$ \large 5^k - 2^k = 3m $$
pour un certain entier \( \large m \).
Pas inductif :
Pour \( \large n=k+1 \) on commence par réécrire les puissances :
$$ \large 5^{k+1} - 2^{k+1} = 5 \cdot 5^k - 2 \cdot 2^k $$
Nous voulons maintenant regrouper un terme avec \( \large (5^k - 2^k) \). C'est pourquoi nous réécrivons \( \large -2 \cdot 2^k \) comme \( \large -5 \cdot 2^k + 3 \cdot 2^k \). Alors on obtient :
$$ \large 5 \cdot 5^k - 2 \cdot 2^k = 5 \cdot 5^k - 5 \cdot 2^k + 3 \cdot 2^k $$
Les deux premiers termes peuvent maintenant être regroupés :
$$ \large = (5^k - 2^k)\cdot 5 + 3 \cdot 2^k $$
Par l'hypothèse d'induction, \( \large 5^k - 2^k \) est divisible par 3, et \( \large 3 \cdot 2^k \) est clairement aussi divisible par 3. Ainsi toute l'expression est divisible par 3, et l'énoncé est démontré pour \( \large n=k+1 \).
Les démonstrations par induction sont un outil central en mathématiques. Elles servent à démontrer des formules, des propriétés de suites, de la divisibilité et bien plus encore.
La méthode montre comment un énoncé peut valoir pour une infinité de nombres en reliant logiquement chaque étape de la suite à la suivante.