Le raisonnement par récurrence

Comment prouver qu’une formule est vraie pour une infinité d’entiers, alors qu’on ne peut en vérifier qu’un nombre fini ? Le raisonnement par récurrence résout ce problème. L’image classique est celle des dominos : si le premier tombe, et si chaque domino qui tombe fait tomber le suivant, alors tous tombent. Le principe est formalisé par Pascal au XVIIe siècle et fait partie des axiomes des entiers naturels formulés par Peano (1889). Voir aussi la logique mathématique.

La rédaction type

1. Énoncer la propriété P(n) clairement.
2. Initialisation : vérifier P(n₀) par un calcul.
3. Hérédité : « Supposons P(n) vraie pour un entier n ≥ n₀ fixé (hypothèse de récurrence). Montrons que P(n + 1) est vraie. » Puis le calcul, en utilisant l’hypothèse.
4. Conclusion : « Par récurrence, P(n) est vraie pour tout n ≥ n₀. »

Exemple 1 : une formule de somme

Propriété : pour tout n ≥ 1, 1 + 2 + … + n = n(n + 1)/2.

• Initialisation : pour n = 1, le membre de gauche vaut 1 et celui de droite 1 × 2/2 = 1. P(1) est vraie.
• Hérédité : supposons 1 + 2 + … + n = n(n + 1)/2. Alors 1 + 2 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n/2 + 1) = (n + 1)(n + 2)/2. C’est exactement P(n + 1).
• Conclusion : la formule est vraie pour tout n ≥ 1.

C’est la formule des nombres triangulaires.

Exemple 2 : une suite définie par récurrence

Énoncé : u₀ = 1 et uₙ₊₁ = 2uₙ + 3. Montrer que uₙ = 4 × 2ⁿ − 3.

• Initialisation : 4 × 2⁰ − 3 = 1 = u₀.
• Hérédité : si uₙ = 4 × 2ⁿ − 3, alors uₙ₊₁ = 2(4 × 2ⁿ − 3) + 3 = 4 × 2ⁿ⁺¹ − 3.
• Conclusion : la formule est vraie pour tout n ≥ 0.

Voir les suites numériques.

Exemple 3 : une inégalité

Propriété : pour tout n ≥ 4, 2ⁿ ≥ n².

• Initialisation à n₀ = 4 : 2⁴ = 16 ≥ 16. Vrai. (P(3) est fausse : 8 < 9.)
• Hérédité : supposons 2ⁿ ≥ n² avec n ≥ 4. Alors 2ⁿ⁺¹ = 2 × 2ⁿ ≥ 2n². Il suffit de montrer 2n² ≥ (n + 1)², soit n² − 2n − 1 ≥ 0, vrai pour n ≥ 3 car n² − 2n − 1 = (n − 1)² − 2 ≥ 2.
• Conclusion : 2ⁿ ≥ n² pour tout n ≥ 4.

Exemple 4 : une divisibilité

Propriété : pour tout n ≥ 0, 4ⁿ − 1 est divisible par 3.

• Initialisation : 4⁰ − 1 = 0, divisible par 3.
• Hérédité : supposons 4ⁿ − 1 = 3k. Alors 4ⁿ⁺¹ − 1 = 4 × 4ⁿ − 1 = 4(3k + 1) − 1 = 12k + 3 = 3(4k + 1).
• Conclusion : vrai pour tout n. (Voir aussi l'arithmétique modulaire, qui le montre directement : 4 ≡ 1 (mod 3).)

Exemple 5 : monotonie et bornes d’une suite

u₀ = 0 et uₙ₊₁ = √(uₙ + 2). Montrons que 0 ≤ uₙ ≤ uₙ₊₁ ≤ 2 pour tout n.

• Initialisation : u₀ = 0 et u₁ = √2 ≈ 1,41 : 0 ≤ 0 ≤ 1,41 ≤ 2.
• Hérédité : si 0 ≤ uₙ ≤ uₙ₊₁ ≤ 2, on ajoute 2 : 2 ≤ uₙ + 2 ≤ uₙ₊₁ + 2 ≤ 4, puis on prend la racine (fonction croissante) : √2 ≤ uₙ₊₁ ≤ uₙ₊₂ ≤ 2.
• Conclusion : la suite est croissante et majorée par 2 ; elle converge (voir la limite d’une suite), et sa limite vaut 2.

Les pièges

Oublier l’initialisation

L’hérédité seule ne suffit pas. La propriété « 10ⁿ + 1 est divisible par 9 » est héréditaire (si 10ⁿ + 1 = 9k, alors 10ⁿ⁺¹ + 1 = 10 × 9k − 9 = 9(10k − 1)), mais elle est fausse pour tout n : 10⁰ + 1 = 2, 10 + 1 = 11…

Utiliser ce qu’on veut démontrer

Dans l’hérédité, on part de P(n) pour arriver à P(n + 1) ; on ne suppose jamais P(n + 1). Et l’on suppose P(n) pour un n donné, pas « pour tout n » (ce serait supposer le résultat).

Le paradoxe des chevaux

« Tous les chevaux ont la même couleur » : la « preuve » par récurrence classique échoue au passage de n = 1 à n = 2, où les deux groupes de n chevaux utilisés ne se chevauchent pas. Une hérédité doit valoir pour tout n ≥ n₀, y compris le premier.

Les variantes

• Récurrence double : on initialise deux rangs et l’on montre que P(n) et P(n + 1) entraînent P(n + 2). Utile pour la suite de Fibonacci.
• Récurrence forte : on suppose P(k) vraie pour tous les k ≤ n. Elle sert, par exemple, à prouver que tout entier ≥ 2 a un diviseur premier (voir la décomposition en facteurs premiers).

Questions fréquentes

Quand utiliser un raisonnement par récurrence ?

Quand une propriété dépend d’un entier n et qu’on peut relier le rang n + 1 au rang n : formules de sommes, suites définies par récurrence, inégalités, divisibilités.

L’initialisation est-elle vraiment indispensable ?

Oui. Sans elle, une propriété héréditaire peut être fausse partout, comme « 10ⁿ + 1 est divisible par 9 ».

Faut-il toujours commencer à n = 0 ?

Non. On initialise au premier rang n₀ où la propriété doit être vraie : 1 pour une somme commençant à 1, 4 pour 2ⁿ ≥ n².

Quelle différence entre récurrence et induction ?

C’est le même principe. « Induction » est le terme anglais (mathematical induction) ; en français, on dit « raisonnement par récurrence ».