Raisonnement par récurrence

Comment démontrer une infinité de propriétés $P(0), P(1), P(2), \dots$ en un nombre fini d'étapes ? En montrant que la première est vraie et que chacune entraîne la suivante : c'est l'effet domino.

  • Comprendre le principe de récurrence
  • Rédiger une démonstration par récurrence
  • Démontrer formules, inégalités, propriétés de suites
  • Éviter les pièges classiques

Cours

1. Principe

Soit $P(n)$ une propriété dépendant d'un entier naturel $n$ et $n_0$ un entier. Si :

  1. Initialisation : $P(n_0)$ est vraie ;
  2. Hérédité : pour tout entier $n \geqslant n_0$, si $P(n)$ est vraie, alors $P(n + 1)$ est vraie ;

alors $P(n)$ est vraie pour tout entier $n \geqslant n_0$.

« Pour tout $n \in \mathbb{N}$, on note $P(n)$ : … »

Initialisation. Pour $n = 0$ : … donc $P(0)$ est vraie.

Hérédité. Soit $n \in \mathbb{N}$. Supposons $P(n)$ vraie (hypothèse de récurrence). Montrons que $P(n + 1)$ est vraie : … (on utilise l'hypothèse).

Conclusion. Par récurrence, $P(n)$ est vraie pour tout entier naturel $n$.

2. Exemples fondamentaux

Montrons que pour tout $n \geqslant 1$ : $1 + 3 + 5 + \dots + (2n - 1) = n^2$.

Initialisation : pour $n = 1$, $1 = 1^2$ ✓.

Hérédité : supposons $1 + 3 + \dots + (2n - 1) = n^2$. Alors $1 + 3 + \dots + (2n - 1) + (2n + 1) = n^2 + 2n + 1 = (n + 1)^2$ : $P(n + 1)$ est vraie.

Conclusion : la formule est vraie pour tout $n \geqslant 1$.

Soit $a$ un réel positif. Pour tout entier naturel $n$ : $(1 + a)^n \geqslant 1 + na$.

Pour tout $n \in \mathbb{N}$, on note $P(n)$ : « $(1 + a)^n \geqslant 1 + na$ ».

Initialisation. $(1 + a)^0 = 1$ et $1 + 0 \times a = 1$ : $P(0)$ est vraie.

Hérédité. Soit $n \in \mathbb{N}$ tel que $(1 + a)^n \geqslant 1 + na$. Comme $1 + a > 0$, on peut multiplier les deux membres par $1 + a$ sans changer le sens : $$(1 + a)^{n+1} \geqslant (1 + na)(1 + a) = 1 + a + na + na^2 = 1 + (n + 1)a + na^2 \geqslant 1 + (n + 1)a$$ car $na^2 \geqslant 0$. Donc $P(n + 1)$ est vraie.

Conclusion. Par récurrence, pour tout $n \in \mathbb{N}$, $(1 + a)^n \geqslant 1 + na$. $\blacksquare$

Cette inégalité sert à démontrer que $q^n \to +\infty$ quand $q > 1$ (chapitre « Limites de suites »).

$u_0 = 1$ et $u_{n+1} = \sqrt{u_n + 6}$. Montrons que pour tout $n$ : $0 \leqslant u_n \leqslant u_{n+1} \leqslant 3$.

Initialisation : $u_0 = 1$, $u_1 = \sqrt7 \approx 2{,}65$ : $0 \leqslant 1 \leqslant \sqrt 7 \leqslant 3$ ✓.

Hérédité : si $0 \leqslant u_n \leqslant u_{n+1} \leqslant 3$, alors $6 \leqslant u_n + 6 \leqslant u_{n+1} + 6 \leqslant 9$, et comme la racine carrée est croissante : $\sqrt6 \leqslant u_{n+1} \leqslant u_{n+2} \leqslant 3$, donc $0 \leqslant u_{n+1} \leqslant u_{n+2} \leqslant 3$ ✓.

La suite est croissante et majorée par 3 (on verra qu'elle converge, vers 3).

3. Pièges

  • Oublier l'initialisation : « si $10^n + 1$ est multiple de 9, alors $10^{n+1} + 1$ aussi » est une hérédité vraie… mais $P(n)$ n'est jamais vraie !
  • Supposer ce qu'on veut démontrer : dans l'hérédité, on suppose $P(n)$ pour un $n$ fixé, pas « pour tout $n$ ».
  • Ne pas utiliser l'hypothèse de récurrence : c'est souvent le signe qu'une récurrence n'était pas nécessaire… ou qu'il y a une erreur.

Le raisonnement par récurrence apparaît implicitement chez al-Karaji (Xe siècle) et chez Pascal (1654, triangle arithmétique). Peano (1889) en fait un axiome des entiers naturels.

Méthodes à connaître

  1. Écris la propriété $P(n)$ précisément.
  2. Initialisation : vérifie $P(n_0)$.
  3. Hérédité : pars de l'hypothèse $P(n)$ et construis $P(n + 1)$ en appliquant la relation de récurrence (souvent : une fonction croissante conserve l'ordre).
  4. Conclusion : « par récurrence, $P(n)$ est vraie pour tout $n \geqslant n_0$ ».

Exemple. $u_{n+1} = \sqrt{u_n + 6}$, $u_0 = 0$ : si $0 \leqslant u_n \leqslant 3$, alors $6 \leqslant u_n + 6 \leqslant 9$ et $\sqrt6 \leqslant u_{n+1} \leqslant 3$.

  1. Pour l'hérédité, écris $S_{n+1} = S_n + (\text{terme de rang } n + 1)$.
  2. Remplace $S_n$ par la formule (hypothèse de récurrence).
  3. Factorise pour retrouver la formule au rang $n + 1$.

Exercices

Démontrer par récurrence que pour tout $n \geqslant 1$ : $1 + 2 + \dots + n = \dfrac{n(n + 1)}{2}$.

Initialisation : $1 = \frac{1 \times 2}{2}$. Hérédité : $\frac{n(n+1)}{2} + (n + 1) = \frac{(n+1)(n + 2)}{2}$.

$u_0 = 2$ et $u_{n+1} = 3u_n - 2$. Démontrer que pour tout $n$, $u_n = 3^n + 1$.

$u_0 = 3^0 + 1 = 2$ ✓. Si $u_n = 3^n + 1$ : $u_{n+1} = 3^{n+1} + 3 - 2 = 3^{n+1} + 1$ ✓.

Démontrer que pour tout $n \in \mathbb{N}$, $4^n - 1$ est un multiple de 3.

$4^0 - 1 = 0$ ✓. Si $4^n - 1 = 3k$ : $4^{n+1} - 1 = 4 \times 4^n - 1 = 4(3k + 1) - 1 = 12k + 3 = 3(4k + 1)$ ✓.

Démontrer que pour tout $n \geqslant 4$ : $2^n \geqslant n^2$. (On admettra que $2n^2 \geqslant (n + 1)^2$ pour $n \geqslant 3$.)

$2^4 = 16 = 4^2$ ✓. Si $2^n \geqslant n^2$ avec $n \geqslant 4$ : $2^{n+1} = 2 \times 2^n \geqslant 2n^2 \geqslant (n+1)^2$ ✓.

$u_0 = 0$ et $u_{n+1} = \frac12 u_n + 2$. Démontrer que pour tout $n$ : $0 \leqslant u_n \leqslant u_{n+1} \leqslant 4$.

$u_1 = 2$ : $0 \leqslant 0 \leqslant 2 \leqslant 4$ ✓. Si $0 \leqslant u_n \leqslant u_{n+1} \leqslant 4$ : la fonction $x \mapsto \frac12x + 2$ est croissante, donc $2 \leqslant u_{n+1} \leqslant u_{n+2} \leqslant 4$ ✓.

Démontrer par récurrence que pour tout $n \geqslant 1$, la dérivée de $x \mapsto x^n$ est $x \mapsto nx^{n-1}$ (utiliser la dérivée d'un produit).

$n = 1$ : $(x)' = 1 = 1 \times x^0$ ✓. Si $(x^n)' = nx^{n-1}$ : $(x^{n+1})' = (x \cdot x^n)' = x^n + x \cdot nx^{n-1} = (n + 1)x^n$ ✓.

Démontrer que $1^3 + 2^3 + \dots + n^3 = \left(\dfrac{n(n+1)}{2}\right)^2$ pour tout $n \geqslant 1$.

Initialisation ✓. Hérédité : $\frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2(n^2 + 4n + 4)}{4} = \frac{(n+1)^2(n+2)^2}{4}$ ✓.