Fiche méthode – Raisonnement par récurrence
Savoir démontrer une propriété pour tout entier naturel grâce à la méthode de récurrence, comprendre ses étapes clés et connaître ses principales applications (encadrements, formules explicites, comportements de suites, sommes).
I. Principe de la récurrence
Pour prouver qu’une propriété $P(n)$ est vraie pour tout entier $n ge n_0$, on suit trois étapes :
- Initialisation : vérifier que $P(n_0)$ est vraie.
- Hérédité : supposer qu’il existe un entier $k ge n_0$ tel que $P(k)$ soit vraie, puis montrer que cela implique $P(k+1)$.
- Conclusion : conclure par la phrase : “D’après le principe de récurrence, la propriété est vraie pour tout $n ge n_0$.”
II. Les 4 cas classiques à connaître
1. Encadrement, majoration, minoration
Dans ce type de question, l’hérédité se fait en partant d’un encadrement portant sur $u_k$ pour construire celui portant sur $u_{k+1}$.
Soit la suite $(u_n)$ définie pour tout entier naturel $n$ par
$$u_{n+1} = dfrac{1}{3}u_n + 2 quadtext{et}quad u_0 = 2.$$
1) Démontrer par récurrence que la suite $(u_n)$ est majorée par $3$.
On veut montrer que, pour tout $n in mathbb{N}$, $u_n le 3$.
Initialisation : pour $n = 0$, on a $u_0 = 2 < 3$. La propriété est vraie au rang $0$.
Hérédité : soit $n$ un entier naturel. Supposons que $u_n < 3$ et montrons que $u_{n+1} < 3$.
De $u_n < 3$ on déduit $,dfrac{1}{3}u_n < dfrac{1}{3} times 3$, donc
$$dfrac{1}{3}u_n + 2 < dfrac{1}{3} times 3 + 2 = 3,$$
c’est-à-dire $u_{n+1} < 3$.
Conclusion : d’après le principe de récurrence, la propriété est vraie pour tout $n in mathbb{N}$ et la suite $(u_n)$ est majorée par $3$.
2. Formule explicite à prouver
Ici, on dispose d’une relation de récurrence entre $u_{n+1}$ et $u_n$, et on veut montrer qu’une expression explicite $u_n = f(n)$ est vraie pour tout $n$.
On considère la suite $(u_n)$ définie par
$$u_{n+1} = 2u_n + 5 quadtext{et}quad u_0 = 7.$$
Montrer par récurrence que, pour tout entier naturel $n$,
$$u_n = 12 cdot 2^n – 5.$$
On veut montrer par récurrence la propriété $P(n)$ définie pour tout $n in mathbb{N}$ par : $$P(n):quad u_n = 12 cdot 2^n – 5.$$
Initialisation : au rang $0$,
$$u_0 = 12 cdot 2^0 – 5 = 12 – 5 = 7,$$
ce qui est bien conforme à l’énoncé ($u_0 = 7$). Donc $P(0)$ est vraie.
Hérédité : soit $k in mathbb{N}$. On suppose $P(k)$ vraie, c’est-à-dire $$u_k = 12 cdot 2^k – 5,$$ et l’on veut montrer $P(k+1)$ : $$u_{k+1} = 12 cdot 2^{k+1} – 5.$$
En utilisant la relation de récurrence : $$u_{k+1} = 2u_k + 5.$$
En remplaçant $u_k$ par son expression :
$$begin{aligned} u_{k+1} &= 2bigl(12 cdot 2^k – 5bigr) + 5 \ &= 24 cdot 2^k – 10 + 5 \ &= 24 cdot 2^k – 5 \ &= 12 cdot 2^{k+1} – 5. end{aligned}$$
La propriété $P(k+1)$ est donc vraie.
Conclusion : d’après le principe de récurrence, pour tout entier naturel $n$, on a $$u_n = 12 cdot 2^n – 5.$$
3. Utilisation d’une fonction
On considère une fonction $f$ telle que $u_{n+1} = f(u_n)$. On exploite alors les propriétés de $f$ (croissance, décroissance, encadrement) pour montrer l’hérédité d’un encadrement sur $(u_n)$.
On considère la suite $(u_n)$ définie par
$$u_{n+1} = sqrt{2u_n + 3} quadtext{et}quad u_0 = 1.$$
Montrer que, pour tout $n in mathbb{N}$, $1 le u_n le 3$.
On veut montrer par récurrence la propriété $P(n)$ : $1 le u_n le 3$ pour tout $n in mathbb{N}$.
Initialisation : pour $n = 0$, $u_0 = 1$ donc $1 le u_0 le 3$. La propriété est vraie au rang $0$.
Hérédité : supposons qu’il existe $n in mathbb{N}$ tel que $1 le u_n le 3$ et montrons que $1 le u_{n+1} le 3$.
On considère la fonction $f$ définie sur l’intervalle $[1;3]$ par $$f(x) = sqrt{2x + 3}.$$
La fonction $f$ est dérivable sur $[1;3]$ et $$f'(x) = dfrac{2}{2sqrt{2x+3}} = dfrac{1}{sqrt{2x+3}} > 0,$$ donc $f$ est strictement croissante sur $[1;3]$.
De $1 le u_n le 3$ et de la croissance de $f$, on obtient $$f(1) le f(u_n) le f(3).$$
Or $f(1) = sqrt{5}$ et $f(3) = 3$, donc $$sqrt{5} le u_{n+1} le 3.$$ Comme $1 < sqrt{5}$, on a bien $1 le u_{n+1} le 3$.
Conclusion : d’après le principe de récurrence, pour tout $n in mathbb{N}$, $1 le u_n le 3$.
4. Somme de type $S_n$
La récurrence permet de prouver des formules de sommes comme $displaystyle S_n = sum_{k=1}^{n} k^2$ ou $sum_{k=1}^{n} k$.
Montrer que, pour tout entier $n ge 1$,
$$sum_{k=1}^{n} k^2 = dfrac{n(n+1)(2n+1)}{6}.$$
On pose $$S_n = sum_{k=1}^{n} k^2.$$
Initialisation : pour $n = 1$,
$$S_1 = 1^2 = 1 quadtext{et}quad dfrac{1 cdot 2 cdot 3}{6} = 1.$$ La formule est vraie au rang $1$.
Hérédité : on suppose la formule vraie au rang $k ge 1$ : $$S_k = dfrac{k(k+1)(2k+1)}{6},$$ et on montre qu’elle est vraie au rang $k+1$ : $$S_{k+1} = dfrac{(k+1)(k+2)(2k+3)}{6}.$$
On écrit $$S_{k+1} = S_k + (k+1)^2.$$ En remplaçant $S_k$ par son expression, puis en factorisant, on retrouve bien la forme $$S_{k+1} = dfrac{(k+1)(k+2)(2k+3)}{6}.$$
Conclusion : par récurrence, la formule est vraie pour tout entier $n ge 1$.
Astuces, pièges et conseils de rédaction
- Bien poser l’hypothèse de récurrence : écrire clairement “On suppose que $P(k)$ est vraie”.
- Dans l’hérédité, partir uniquement de $P(k)$ pour arriver à $P(k+1)$.
- Travailler proprement les expressions algébriques, sans sauter d’étapes clés.
- Utiliser une fonction $f$ lorsque la suite est donnée par $u_{n+1} = f(u_n)$ afin de gérer croissance ou encadrement.
- Oublier l’étape d’initialisation ou la traiter de manière incomplète.
- Ne pas annoncer l’hypothèse de récurrence avant de l’utiliser.
- Tenter de faire l’hérédité sans utiliser $P(k)$ (raisonnement non valide).
- Oublier la conclusion finale faisant explicitement référence au principe de récurrence.
- Bien séparer les trois parties : Initialisation, Hérédité, Conclusion.
- Rédiger avec des phrases complètes et précises (pas seulement des calculs).
- Ne jamais supposer deux choses différentes en même temps dans l’hérédité.
- Terminer par une phrase du type : “La propriété est vraie pour tout $n ge n_0$.”