Récurrence et suites
Tu observes sur les premiers termes d'une suite que $u_n = 2 + 3n$. Cela marche pour $n = 0$, $1$, $2$, $10$… Mais peux-tu être sûr que cela marche pour tous les entiers, jusqu'à $n = 10^{9}$ et au-delà ? Tester un nombre fini de cas ne prouve rien. Le raisonnement par récurrence permet de démontrer une propriété pour une infinité d'entiers, en deux étapes seulement.
Le principe de récurrence
Pense à une file infinie de dominos. Deux choses suffisent pour qu'ils tombent tous :
-
le premier tombe ;
-
chaque domino qui tombe fait tomber le suivant.
Pourquoi ça marche ? $P(0)$ est vraie, donc $P(1)$ aussi par l'hérédité, donc $P(2)$, puis $P(3)$… Aucun entier ne peut échapper à cet enchaînement.
Une rédaction complète comporte toujours quatre éléments : l'énoncé de $P(n)$, l'initialisation, l'hérédité (on suppose $P(n)$ pour un $n$ fixé, c'est l'hypothèse de récurrence, et on en déduit $P(n+1)$), puis la conclusion.
Soit $(u_n)$ la suite définie par $u_0 = 2$ et, pour tout entier naturel $n$, $u_{n+1} = u_n + 3$. Montrer par récurrence que, pour tout entier naturel $n$,…
Soit $(u_n)$ la suite définie par $u_0 = 2$ et, pour tout entier naturel $n$, $u_{n+1} = u_n + 3$.
Montrer par récurrence que, pour tout entier naturel $n$, $u_n = 2 + 3n$.
Démontrer une formule explicite
Une suite est souvent donnée par une relation de récurrence $u_{n+1} = f(u_n)$. Si on conjecture une formule explicite pour $u_n$, la récurrence permet de la démontrer.
Dans l'hérédité, garde en tête le but : écris à côté de ton calcul ce que tu dois obtenir (ici $3^{n+2} + 1$). Cela guide les simplifications.
Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = 2u_n + 1$. Montrer par récurrence que, pour tout entier naturel $n$, $u_n = 2^{n+1} - 1$.
Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = 2u_n + 1$.
Montrer par récurrence que, pour tout entier naturel $n$, $u_n = 2^{n+1} - 1$.
Pour tout entier naturel $n$, on pose $S_n = 1 + 2 + 3 + \cdots + n$. a) Montrer par récurrence que $S_n = \dfrac{n(n+1)}{2}$. b) Montrer par récurrence que, pour tout…
Pour tout entier naturel $n$, on pose $S_n = 1 + 2 + 3 + \cdots + n$.
- a) Montrer par récurrence que $S_n = \dfrac{n(n+1)}{2}$.
- b) Montrer par récurrence que, pour tout entier $n \geq 1$, $1^3 + 2^3 + \cdots + n^3 = S_n^2$.
Démontrer une inégalité
On démontre aussi par récurrence des inégalités du type $u_n \geq a$, $u_n \leq b$ ou $0 \leq u_n \leq 3$. L'idée est de partir de l'hypothèse de récurrence et de transformer l'inégalité (en ajoutant, multipliant par un nombre positif, ou en appliquant une fonction croissante) jusqu'à obtenir celle du rang $n+1$.
Montrer qu'une suite est monotone
Deux méthodes, à choisir selon la situation.
-
Par le signe de $u_{n+1} - u_n$. On calcule la différence, on utilise un encadrement déjà démontré pour trouver son signe.
-
Par récurrence, avec $P(n)$ : « $u_n \leq u_{n+1}$ », en utilisant que $f$ est croissante : $u_n \leq u_{n+1} \Rightarrow f(u_n) \leq f(u_{n+1})$, c'est-à-dire $u_{n+1} \leq u_{n+2}$.
Montrer par récurrence que, pour tout entier naturel $n$, $2^n \geq n + 1$.
Montrer par récurrence que, pour tout entier naturel $n$, $2^n \geq n + 1$.
Soit $(u_n)$ la suite définie par $u_0 = 5$ et $u_{n+1} = \dfrac{1}{2}u_n + 2$. a) Montrer par récurrence que, pour tout entier naturel $n$, $u_n \geq 4$. b) Montrer par…
Soit $(u_n)$ la suite définie par $u_0 = 5$ et $u_{n+1} = \dfrac{1}{2}u_n + 2$.
- a) Montrer par récurrence que, pour tout entier naturel $n$, $u_n \geq 4$.
- b) Montrer par récurrence que la suite $(u_n)$ est décroissante.
L'inégalité de Bernoulli
Une population augmente de $5\ \%$ chaque heure. Au bout de $n$ heures, elle est multipliée par $1{,}05^n$. Cette quantité est-elle au moins égale à $1 + 0{,}05\,n$ ? L'inégalité de Bernoulli répond à cette question, et elle est très utile pour étudier la suite $(q^n)$.
Remarque bien l'astuce de l'hérédité : on multiplie l'hypothèse de récurrence par un facteur positif, puis on minore en supprimant un terme positif ($na^2$).
Limite de la suite $(q^n)$
Si $q > 1$, on écrit $q = 1 + a$ avec $a = q - 1 > 0$. L'inégalité de Bernoulli donne $q^n \geq 1 + n(q-1)$. Le membre de droite tend vers $+\infty$ ; on conclut avec le théorème de comparaison ci-dessous. Donc $\lim\limits_{n\to+\infty} q^n = +\infty$.
Pourquoi $0$ pour $-1
Soit $a$ un réel strictement positif. a) Énoncer l'inégalité de Bernoulli pour tout entier naturel $n$ : $(1+a)^n \geq \ldots$ puis la démontrer par récurrence. b) Une…
Soit $a$ un réel strictement positif.
- a) Énoncer l'inégalité de Bernoulli pour tout entier naturel $n$ : $(1+a)^n \geq \ldots$ puis la démontrer par récurrence.
- b) Une population de bactéries augmente de $5\ \%$ chaque heure. Montrer que, au bout de $n$ heures, elle a été multipliée par au moins $1 + 0{,}05n$.
Étudier une suite : limite et vitesse de convergence
Pour une suite $u_{n+1} = f(u_n)$, on enchaîne souvent trois questions :
-
Encadrement par récurrence : $a \leq u_n \leq b$ ;
-
Monotonie : signe de $u_{n+1} - u_n$ ou récurrence ;
-
Limite : le théorème de convergence monotone donne l'existence de $\ell$, et un encadrement du type $0 \leq \ell - u_n \leq k\,q^n$ avec $0 < q < 1$ donne la limite grâce au théorème des gendarmes.
Cette dernière étape se fait en deux temps : on prouve une inégalité de contraction $\ell - u_{n+1} \leq q(\ell - u_n)$, puis, par récurrence, $\ell - u_n \leq (\ell - u_0)\,q^n$.
Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = \sqrt{2 + u_n}$. a) Montrer par récurrence que, pour tout entier naturel $n$, $0 < u_n < 2$. b) Montrer que la…
Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = \sqrt{2 + u_n}$.
- a) Montrer par récurrence que, pour tout entier naturel $n$, $0 < u_n < 2$.
- b) Montrer que la suite $(u_n)$ est croissante.
- c) Montrer que, pour tout $n$, $2 - u_{n+1} \leq \dfrac{1}{2}(2 - u_n)$, puis en déduire que $2 - u_n \leq \dfrac{1}{2^n}$.
Soit $(u_n)$ la suite définie par $u_0 = 0$ et $u_{n+1} = \dfrac{2u_n + 3}{u_n + 4}$. a) Montrer par récurrence que, pour tout $n$, $0 \leq u_n \leq 1$. b) Montrer que,…
Soit $(u_n)$ la suite définie par $u_0 = 0$ et $u_{n+1} = \dfrac{2u_n + 3}{u_n + 4}$.
- a) Montrer par récurrence que, pour tout $n$, $0 \leq u_n \leq 1$.
- b) Montrer que, pour tout $n$, $u_{n+1} - u_n = \dfrac{(1-u_n)(u_n+3)}{u_n+4}$, puis que $(u_n)$ est croissante.
- c) Montrer par récurrence que $1 - u_n \leq \left(\dfrac{1}{2}\right)^n$ pour tout $n$ et en déduire la limite de $(u_n)$.
Suites d'intégrales
On rencontre aussi des suites définies par une intégrale dépendant de $n$. Les outils sont :
-
l'intégration par parties pour trouver une relation entre $I_{n+1}$ et $I_n$ ;
-
la positivité et la croissance de l'intégrale pour encadrer $I_n$ ;
-
le théorème des gendarmes pour la limite.
Pour tout entier naturel $n$, on pose $I_n = \displaystyle\int_0^1 x^n e^{x}\,dx$. a) Calculer $I_0$ et $I_1$. b) Montrer que, pour tout entier $n \geq 0$,…
Pour tout entier naturel $n$, on pose $I_n = \displaystyle\int_0^1 x^n e^{x}\,dx$.
- a) Calculer $I_0$ et $I_1$.
- b) Montrer que, pour tout entier $n \geq 0$, $I_{n+1} = e - (n+1)I_n$.
- c) Montrer que, pour tout $n$, $0 \leq I_n \leq \dfrac{e}{n+1}$, puis déterminer $\lim_{n\to+\infty} I_n$.
L'essentiel
-
Principe de récurrence : si $P(n_0)$ est vraie (initialisation) et si, pour tout $n \geq n_0$, $P(n) \Rightarrow P(n+1)$ (hérédité), alors $P(n)$ est vraie pour tout $n \geq n_0$.
-
Une rédaction complète comprend : l'énoncé de $P(n)$, l'initialisation, l'hérédité avec hypothèse de récurrence clairement posée, et la conclusion.
-
Pour une formule ou une somme, on remplace $u_n$ (ou $S_n$) par l'hypothèse de récurrence et on simplifie pour retrouver le rang $n+1$.
-
Pour une inégalité, on transforme l'hypothèse de récurrence en respectant le sens (multiplier par un nombre positif, additionner, appliquer une fonction croissante).
-
Bernoulli : $(1+a)^n \geq 1 + na$ pour $a > 0$ ; il sert à démontrer $q^n \to +\infty$ si $q > 1$.
-
Pour une suite $u_{n+1} = f(u_n)$ : encadrement, monotonie, puis limite par comparaison ou théorème des gendarmes.
-
Valeur de la limite : si $f$ est continue sur un intervalle $I$ avec $f(I) \subset I$ et si $(u_n)$ converge vers $\ell$, alors $\ell = f(\ell)$ : comme $f$ est continue, $f(u_n) \to f(\ell)$, et $u_{n+1} = f(u_n) \to \ell$ ; par unicité de la limite, $\ell = f(\ell)$.
-
Pour une suite d'intégrales : intégration par parties pour la relation de récurrence, positivité de l'intégrale pour l'encadrement.
Retour au début : tu ne peux pas vérifier une infinité de cas un par un, mais l'initialisation et l'hérédité suffisent pour tous les traiter d'un coup.