Récurrence et propriétés de suites
Une file de dominos est alignée sur la table. Tu sais que le premier tombe, et que si un domino tombe, alors le suivant tombe aussi. Peux-tu en conclure que tous les dominos tombent, même s'il y en a une infinité ? C'est exactement l'idée du raisonnement par récurrence, outil indispensable pour démontrer une propriété valable « pour tout entier naturel $n$ ».
Le principe de récurrence
Une suite définie par $u_{n+1}=f(u_n)$ se construit de proche en proche. Pour démontrer une propriété de tous ses termes, on procède de la même façon : de proche en proche.
Dans l'hérédité, l'hypothèse « $P(n)$ est vraie » s'appelle l'hypothèse de récurrence. On ne la démontre pas : on la suppose, pour un $n$ fixé quelconque, et on en déduit $P(n+1)$.
Démontrer par récurrence que, pour tout entier naturel $n$, $\displaystyle \sum_{k=0}^{n} (2k+1) = (n+1)^2$.
Démontrer par récurrence que, pour tout entier naturel $n$, $\displaystyle \sum_{k=0}^{n} (2k+1) = (n+1)^2$.
On considère la suite $(u_n)$ définie par $u_0 = 2$ et, pour tout entier naturel $n$, $u_{n+1} = 3u_n - 2$. Démontrer par récurrence que, pour tout entier naturel $n$,…
On considère la suite $(u_n)$ définie par $u_0 = 2$ et, pour tout entier naturel $n$, $u_{n+1} = 3u_n - 2$.
Démontrer par récurrence que, pour tout entier naturel $n$, $u_n = 3^n + 1$.
Démontrer une inégalité ou une divisibilité
La rédaction est identique, mais l'hérédité demande une petite astuce : on part de l'hypothèse de récurrence et on la transforme (multiplication, addition) jusqu'à obtenir la forme du rang $n+1$.
Pour la divisibilité, on écrit le terme du rang $n+1$ en faisant apparaître le terme du rang $n$ : par exemple, si $3\mid a_n$ alors $a_n=3k$ avec $k$ entier, et on exprime $a_{n+1}$ à l'aide de $k$.
Démontrer par récurrence que, pour tout entier naturel $n$, $2^n \geqslant n + 1$.
Démontrer par récurrence que, pour tout entier naturel $n$, $2^n \geqslant n + 1$.
Démontrer par récurrence que, pour tout entier naturel $n \geqslant 1$, $4^n + 6n - 1$ est divisible par $9$. Démontrer ensuite par récurrence que, pour tout entier…
Démontrer par récurrence que, pour tout entier naturel $n \geqslant 1$, $4^n + 6n - 1$ est divisible par $9$.
Démontrer ensuite par récurrence que, pour tout entier naturel $n \geqslant 4$, $2^n \geqslant n^2$.
Propriétés de suites : encadrement, monotonie, convergence
Pour une suite définie par $u_{n+1}=f(u_n)$, la récurrence est l'outil naturel :
-
bornes : on montre $a\leqslant u_n\leqslant b$ en appliquant $f$ à l'hypothèse de récurrence (si $f$ est croissante sur l'intervalle, l'ordre est conservé) ;
-
monotonie : on montre $u_n\leqslant u_{n+1}$ (ou $\geqslant$) pour tout $n$, de même en appliquant $f$.
Si $(u_n)$ est croissante et majorée, elle converge (théorème de convergence monotone, admis). Si elle est croissante et non majorée, elle tend vers $+\infty$.
Démonstration. Soit $A$ un réel quelconque. Comme $(u_n)$ n'est pas majorée, $A$ n'est pas un majorant : il existe un rang $N$ tel que $u_N>A$. Comme la suite est croissante, pour tout $n\geqslant N$, $u_n\geqslant u_N>A$. Ainsi l'intervalle $[A\,;+\infty[$ contient tous les termes à partir du rang $N$ : $\lim u_n=+\infty$.
Conséquence (comparaison) : si $u_n\geqslant v_n$ à partir d'un certain rang et si $v_n\to+\infty$, alors $u_n\to+\infty$. En effet, tout intervalle $[A\,;+\infty[$ contient les $v_n$ à partir d'un rang $N$, donc aussi les $u_n$ à partir du plus grand des deux rangs.
Parfois on veut montrer que $(u_n)$ se rapproche d'une limite $\ell$ : on établit $|u_{n+1}-\ell|\leqslant k\,|u_n-\ell|$ avec $0 Démonstration. Initialisation : $n=0$, $1\geqslant 1$. Hérédité : si $(1+a)^n\geqslant 1+na$, comme $1+a>0$, Conséquence : si $q>1$, on pose $q=1+a$ avec $a>0$ ; alors $q^n\geqslant 1+na\to+\infty$, donc $\lim q^n=+\infty$ (par comparaison). Par exemple $1{,}02^n\to+\infty$ : un placement à $2\ \%$ par an finit par dépasser n'importe quelle somme. Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = \sqrt{2u_n + 3}$ pour tout entier naturel $n$. Soit $a$ un réel strictement positif. Démontrer par récurrence l'inégalité de Bernoulli : pour tout entier naturel $n$, $(1+a)^n \geqslant 1 + na$. En déduire la limite de la suite $(1{,}02^n)$ quand $n$ tend vers $+\infty$. Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = \dfrac{u_n + 4}{u_n + 1}$ pour tout entier naturel $n$.L'inégalité de Bernoulli
Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = \sqrt{2u_n + 3}$ pour tout entier naturel $n$. a) Démontrer par récurrence que, pour tout entier naturel $n$,…
Soit $a$ un réel strictement positif. Démontrer par récurrence l'inégalité de Bernoulli : pour tout entier naturel $n$, $(1+a)^n \geqslant 1 + na$. En déduire la limite…
Soit $(u_n)$ la suite définie par $u_0 = 1$ et $u_{n+1} = \dfrac{u_n + 4}{u_n + 1}$ pour tout entier naturel $n$. a) Démontrer par récurrence que, pour tout entier…
Conjecturer puis démontrer : formules explicites et matrices
Souvent, on calcule les premiers termes, on conjecture une formule, puis on la démontre par récurrence. La conjecture n'est jamais une preuve.
Le même schéma sert pour les formules explicites de suites (comme $u_n=3^n+1$ à partir de $u_{n+1}=3u_n-2$ : $3(3^n+1)-2=3^{n+1}+1$) : dans l'hérédité, on remplace $u_n$ par sa formule dans la relation de récurrence.
Pour la suite de Fibonacci ($F_{n+2}=F_{n+1}+F_n$), l'hérédité utilise deux rangs : on écrit $F_{n+2}$ avec la relation, et on applique l'hypothèse. Si l'hérédité fait intervenir $P(n)$ et $P(n-1)$, on initialise à deux rangs consécutifs.
On considère la matrice $A = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$. a) Calculer $A^2$ et $A^3$. b) Conjecturer l'expression de $A^n$ pour tout entier naturel…
On considère la matrice $A = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$.
- a) Calculer $A^2$ et $A^3$.
- b) Conjecturer l'expression de $A^n$ pour tout entier naturel $n$.
- c) Démontrer cette conjecture par récurrence.
On considère la suite de Fibonacci définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$ pour tout entier naturel $n$. a) Démontrer par récurrence que, pour tout…
On considère la suite de Fibonacci définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$ pour tout entier naturel $n$.
- a) Démontrer par récurrence que, pour tout entier naturel $n$, $\displaystyle \sum_{k=0}^{n} F_k = F_{n+2} - 1$.
- b) Démontrer par récurrence que, pour tout entier naturel $n \geqslant 1$, $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$.