Suites et récurrence

Raisonnement par récurrence

Lorsque l’on souhaite démontrer une proposition mathématique qui dépend d’un entier \(n\), il est parfois possible de démontrer cette proposition par récurrence.
Pour tout entier \(n\), on note \(\mathcal{P}(n)\) la proposition qui nous intéresse. La démonstration par récurrence comporte trois étapes

  • Initialisation : On montre qu’il existe un entier \(n_0\) pour lequel \(\mathcal{P}(n_0)\) est vraie ;
  • Hérédité : on montre que, si pour un certain entier \(n\geqslant n_0\), \(\mathcal{P}(n)\) est vraie, alors \(\mathcal{P}(n+1)\) l’est également ;
  • Conclusion : on en conclut que pour entier \(n\geqslant n_0\), la proposition \(\mathcal{P}(n)\) est vraie.

Le principe du raisonnement par récurrence rappelle les dominos que l’on aligne et que l’on fait tomber, les uns à la suite des autres.

On positionne les dominos de telle sorte que, dès que l’un tombe, peu importe lequel, il entraîne le suivant dans sa chute. C’est l’hérédité. Seulement, encore faut-il faire effectivement tomber le premier domino, sans quoi rien ne se passe : c’est l’initialisation.

Si ces deux conditions sont remplies, on est certain qu’à la fin, tous les dominos seront tombés : c’est notre Conclusion.

Exemple :On considère la suite \((u_n)\) définie par \(u_0=4\) et, pour tout entier naturel \(n\), \(u_{n+1}=3u_n -2\).

A l’aide de cette expression, il est possible de calculer les termes de la suite de proche en proche.

  • \(u_1 = 3 u_0 – 2 = 3 \times 4 -2 = 10\).
  • \(u_2=3u_1 – 2 = 3 \times 10 – 2 = 28\).
  • \(\ldots\)

On souhaite déterminer une expression de \(u_n\) en fonction de \(n\) pour tout entier naturel \(n\).

Pour \(n\in\mathbb{N}\), on note \(\mathcal{P}(n)\) la proposition « \(u_n=1+3^{n+1}\) ».

  • Initialisation : Pour \(n=0\). \(1+3^{0+1}=1+3=4=u_0\). La propriété est vraie au rang 0.
  • Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie. On a donc \(u_n = 1+3^{n+1}\). Ainsi,
    \[u_{n+1}= 3u_n-2=3(1+3^{n+1})-2=3\times 1 + 3 \times 3^{n+1}-2=1+3^{n+2}=1+3^{(n+1)+1}\]
    On a donc \(u_{n+1}=1+3^{(n+1)+1}\). \(\mathcal{P}(n+1)\) est donc vraie. \(\mathcal{P}\) est héréditaire.
  • Conclusion : La propriété est vraie au rang 0 et est héréditaire, elle est donc vraie pour tout entier \(n\).

Inégalité de Bernoulli : Soit \(a\) un réel strictement positif. Pour tout entier naturel \(n\), \((1+a)^n \geqslant 1+na\)

Démonstration :Nous allons démontrer cette propriété par récurrence. Pour un entier naturel \(n\), on note \(\mathcal{P}(n)\) la proposition « \((1+a)^n \geqslant 1+na\) ».

  • Initialisation : Prenons \(n=0\). \((1+a)^0 = 1\) et \(1+ 0 \times a = 1\). On a bien \((1+a)^0 \geqslant 1+0 \times a\). \(\mathcal{P}(0)\) est donc vraie.
  • Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie. On a donc \((1+a)^n \geqslant 1+na\).En multipliant des deux côtés de l’inégalité par \((1+a)\), qui est strictement positif, on obtient \((1+a)^{n+1}\geqslant (1+na)(1+a)\). Or,
    \[(1+na)(1+a)=1+na+a+na^2=1+(n+1)a+na^2 \geqslant 1+(n+1)a\]Ainsi, \((1+a)^{n+1} \geqslant 1+(n+1)a\). \(\mathcal{P}(n+1)\) est donc vraie.
  • Conclusion : \(\mathcal{P}(0)\) est vraie et, si \(\mathcal{P}(n)\) est vraie, \(\mathcal{P}(n+1)\) est vraie. Ainsi, d’après le principe de récurrence, \(\mathcal{P}(n)\) est vraie pour tout entier naturel \(n\).
La droite d’équation \(y=1+nx\) n’est autre que la tangente à la courbe d’équation \(y=(1+x)^n\) à l’abscisse 0. L’inégalité de Bernoulli dit donc que la courbe se trouve au-dessus de la tangente lorsque \(x>0\).

Suite majorée, minorée, bornée

Soit \((u_n)\) une suite réelle. On dit que…

  • …\((u_n)\) est majorée s’il existe un réel \(M\) tel que, pour tout entier naturel \(n\), \(u_n \leqslant M\).
  • …\((u_n)\) est minorée s’il existe un réel \(m\) tel que, pour tout entier naturel \(n\), \(u_n \geqslant m\).
  • …\((u_n)\) est bornée si \((u_n)\) est à la fois majorée et minorée.
Les majorants et minorants sont indépendants de \(n\) ! Bien que pour tout \(n>0\), on ait \(n \leqslant n^2\), on ne peut pas dire que la suite \((u_n)\) définie par \(u_n=n\) est majorée.

Exemple : Pour tout \(n\), on pose \(u_n=\cos (n)\). La suite \((u_n)\) est bornée puisque, pour tout entier \(n\), \(-1 \leqslant u_n \leqslant 1\).

Exemple : Pour tout entier naturel \(n\), on pose \(v_n=n^2+1\). La suite \((v_n)\) est minorée puisque pour tout \(n\), \(v_n\geqslant 1\). En revanche, elle n’est pas majorée.

Exemple : Pour tout entier naturel \(n\), on pose \(w_n=(-1)^n \, n\). La suite \((w_n)\) n’est ni majorée, ni minorée.

Lorsque la suite est définie par récurrence, une majoration ou une minoration peut être démontrée par récurrence.

Exemple : On considère la suite \((u_n)\) définie par \(u_0 = 5\) et pour tout entier naturel \(n\), \(u_{n+1}=0.5u_n + 2\). Pour tout entier naturel \(n\), on note \(\mathcal{P}(n)\) la proposition « \(u_n \geqslant 4\) ».

  • Initialisation : On a bien \(u_0 \geqslant 4\). \(\mathcal{P}(0)\) est donc vraie.
  • Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie, c’est-à-dire \(u_n \geqslant 4\). Ainsi, \(0.5 u_n \geqslant 2\) et \(0.5u_n+2 \geqslant 4\), c’est-à-dire \(u_{n+1}\geqslant 4\). \(\mathcal{P}(n+1)\) est vraie.
  • Ainsi, \(\mathcal{P}(0)\) est vraie et la proposition \(\mathcal{P}\) est héréditaire. D’après le principe de récurrence, on en conclut que pour tout entier naturel \(n\), \(\mathcal{P}(n)\) est vraie.

Suites croissantes, suites décroissantes

Soit \((u_n)\) une suite réelle.

  • On dit que \((u_n)\) est croissante à partir de \(n_0\) si, pour tout entier naturel \(n\geqslant n_0\), \(u_{n+1} \geqslant u_n\).
  • On dit que \((u_n)\) est décroissante à partir de \(n_0\) si, pour tout entier naturel \(n\geqslant n_0\), \(u_{n+1} \geqslant u_n\).
Lorsqu’une suite est définie par récurrence, ses variations peuvent également être étudiées par récurrence.

Exemple : On considère la suite \((u_n)\) définie par \(u_0=4\) et telle que, pour tout entier naturel \(n\), \(u_{n+1}=\sqrt{5+u_n}\).

Pour tout entier naturel \(n\), on note \(\mathcal{P}(n)\) la proposition \(0\leqslant u_{n+1} \leqslant u_n\). Montrons que \(\mathcal{P}(n)\) est vraie pour tout \(n\). On démontrera ainsi que la suite \((u_n)\) est décroissante et minorée par 0, un résultat qui nous intéressera fortement dans un prochain chapitre

  • Initialisation : \(u_0=4\), \(u_1=\sqrt{5+4}=\sqrt{9}=3\). On a bien \(0 \leqslant u_1 \leqslant u_0\). \(\mathcal{P}(0)\) est vraie.
  • Hérédité : Soit \(n\in\mathbb{N}\). Supposons que \(\mathcal{P}(n)\) est vraie. On a alors
    \[0\leqslant u_{n+1} \leqslant u_n\]
    En ajoutant 5 à chaque membre, on obtient
    \[5\leqslant u_{n+1} +5\leqslant u_n+5\]
    On souhaite « appliquer la racine carrée » à cette inégalité. La fonction \(x\mapsto \sqrt{x}\) étant croissante, l’appliquer ne changera pas le sens de l’inégalité. On a donc bien
    \[ \sqrt{5} \leqslant \sqrt{u_{n+1}+5} \leqslant \sqrt{u_n+5}\]
    D’une part, \(\sqrt{5}>0\). D’autre part, \(\sqrt{u_{n+1}+5}=u_{n+2}\) et \(\sqrt{u_{n}+5}=u_{n+1}\). Ainsi
    \[0 \leqslant u_{n+2} \leqslant u_{n+1}\]
    La proposition \(\mathcal{P}(n+1)\) est donc vraie.
  • Conclusion : \(\mathcal{P}(0)\) est vraie et \(\mathcal{P}\) est héréditaire. Par récurrence, \(\mathcal{P}(n)\) est vraie pour tout entier naturel \(n\).