Raisonnement par récurrence
Le terme de récurrence vient d'un verbe latin qui signifie courir en arrière, mais ce n'est pas une raison pour vous sauver. En effet, vous trouverez sur cette page un mode de raisonnement. Non pas le truc qui révolutionnera votre façon de penser mais une façon simple d’aborder un certain type de problème mathématique et de procéder à des démonstrations.
En terminale générale, on apprend que la récurrence consiste à définir le terme d’une suite par celui qui le précède ; on l'utilise comme moyen de démonstration. Cet outil dépasse d'ailleurs largement l'étude des suites et des séries (pour l'étude des dérivées successives, par exemple). Historiquement, il est possible que le triangle de Pascal ait été son premier support.
Ainsi, une suite arithmétique est définie par une relation de type \(u_n = u_{n-1} + r\) et une suite géométrique par une relation de type \(u_n = qu_{n-1}\) (avec \(n\) entier naturel, \(r\) et \(q\) réels non nuls).
Utilisation avec tableur
Les tableurs sont un excellent outil pour utiliser une relation de récurrence pas trop alambiquée puisqu'il suffit d'un cliquer-glisser sur la formule (exemples simples en pages suite géométrique avec Excel et limites de suites avec Excel). La relation de récurrence peut aussi être traitée par une calculatrice (voir la page sur les suites arithmétiques avec calculatrices).
Utilisation dans les démonstrations
Le raisonnement par récurrence est souvent adapté pour démontrer un résultat dont l'énoncé commence par « pour tout \(n\) appartenant à \(\mathbb{N}\), on a... »
Raisonnement par récurrence
L’axiome de récurrence stipule que si une propriété \(P\) est vraie en 0 et en \(n \in \mathbb{N}\) (que l’on note \(P(n)\)) et que cette véracité en \(n\) implique que \(P(n + 1 )\) est également vraie, alors \(P(n)\) est vraie quel que soit \(n.\) \(P(n)\) est dite héréditaire.
Un raisonnement par récurrence réalisé dans les règles de l’art consiste à énoncer la propriété, à établir que cette dernière se vérifie pour la plus petite valeur admise de \(n\) (souvent 0 ou 1), c’est-à-dire à initialiser la récurrence puis à démontrer que la propriété est héréditaire. Enfin, on conclut.
Un petit exemple théorique ? Oui ? D’accord.
Prouver que la suite suivante \((u_n)\) est croissante sur \(\mathbb{N}\) sachant que \(u_0 = 0\) :
\[u_{n+1} = \sqrt{4 + u_n^2}\]
Énonçons la propriété à démontrer : on pose \(P(n)\) : \(u_{n+1} > u_n.\)
Initialisation : calculons le premier terme. \(u_1 = 2.\) Donc, \(P(0)\) est vraie puisque \(u_1 > u_0.\)
Hérédité : supposons que \(P(n)\) est vraie pour un entier naturel \(n\) fixé.
\(u_{n + 1} > u_n\) \(\Rightarrow u_{n + 1}^2 > u_n^2\) \(\Rightarrow 4 + u_{n+1}^2 > 4 + u_n^2\) \(\Rightarrow \sqrt{4 + u_{n+1}^2} > \sqrt{4 + u_n^2}\)
Quel que soit \(n,\) \(u_{n+1} > u_n\) et \(P(n + 1)\) est vraie.
Conclusion : \(P(0)\) est vraie et pour tout \(n\) entier naturel \(P(n)\) est vraie. La suite est croissante.
Deuxième exemple : soit la suite \((u_n)\) définie sur \(\mathbb{N}\) par \(u_0 = 5000\) et \(u_{n+1} = 1,04u_n + 1000.\) Démontrer que pour tout \(n \in \mathbb{N}\) on a \(u_n\) \(= 30\,000 × 1,04^n - 25\,000\) (il s'agit de vérifier le résultat de l'exercice 2 de la page sur les suites arithmético-géométriques).
\(P(n)\) : \(u_n\) \(= 30\,000 × 1,04^n - 25\,000\)
Initialisation : \(30\,000 × 1,04^0 - 25\,000\) \(= 5000\) ce qui signifie que \(P(0)\) est vraie.
Hérédité : supposons que l'égalité \(P(n)\) est vraie pour un entier \(n.\)
\(u_{n+1} = 30\,000 × 1,04^{n+1} - 25\,000\)
\(\Leftrightarrow u_{n+1} = 30\,000 × 1,04^{n+1} - 26\,000 + 1000\)
\(\Leftrightarrow u_{n+1} = 30\,000 × 1,04 \times 1,04^n - (25\,000 \times 1,04) + 1000\)
\(\Leftrightarrow u_{n+1} = 1,04(30\,000 × 1,04^n - 25\,000) + 1000\)
\(\Leftrightarrow u_{n+1} = 1,04u_n + 1000\)
Donc \(P(n)\) est vraie pour tout entier \(n.\)
Vous remarquerez que l'on suppose \(P(n)\) vraie pour UN entier puis que l'on conclut qu'elle l'est pour TOUT entier.
Voir d'autres exemples : somme de premiers entiers, limites des suites de type \(q^n\), complexes et suites au bac, marche aléatoire au bac (spé maths), limite d'une suite définie par \(u_{n+1} = f(u_n)\), exercice de suite avec logarithme, démonstrations de propriétés des complexes, du binôme de Newton, de la formule de Moivre et du petit théorème de Fermat (terminale maths expertes) ...
Compléments (hors programme de terminale)
1- La récurrence forte
La démonstration est un peu différente. Comme pour la récurrence simple, on vérifie d’abord que \(P(0)\) est vraie. Ensuite, on vérifie que \(P(n)\) est vraie jusqu’au rang \(n,\) qu’elle est également vraie pour \(P(n+1)\) et donc que la propriété se vérifie pour tout entier naturel.
2- La récurrence d’ordre \(n\) (processus discrets)
Si la propriété \(P(n+2)\) dépend à la fois de \(P(n)\) et de \(P(n+1),\) nous sommes dans le cadre d’une récurrence d’ordre 2.
Exemple : soit la suite \((u_n)\) définie par \(u_0 = 1,\) \(u_1 = 3\) et \(u_{n+2} = 4u_{n+1} - 3u_n.\)
Montrer que, \(\forall n \in \mathbb{N},\) \(u_n = 3^n.\)
Initialisation : la proposition est vraie pour \(u_0\) qui est égal à \(3^0\) et pour \(u_1\) qui est égal à \(3^1.\)
Hérédité : considérons la proposition comme vraie. Nous avons donc \(u_n\) qui est égal à \(3^n\) et \(u_{n+1}\) qui est égal à \(3^{n+1}.\)
Donc, \(u_{n+2}\) \(= (4 × 3^{n+1}) - ((3 × 3^n)\) \(= 3^n[(4 × 3) - 3]\) \(= 3^n × 9\) \(= 3^n × 3^2\) \(= 3^{n+2}.\)
Nous avons montré par récurrence que \(P(n + 2)\) était vraie.
3- Applications statistiques et professionnelles
On peut définir une prévision par régression linéaire simple non pas en utilisant sa droite de tendance de type \(y = at + b\) mais avec \(y_n = y_{n-1} + a\) (\(n\) étant un entier naturel, correspondant ici à une date), c'est-à-dire en utilisant la prévision précédente.
Ce mode de calcul est utilisé dans certaines techniques prévisionnelles, notamment les lissages exponentiels (LES, LED, lissage de Holt, lissage de Winters additif, lissage de Winters multiplicatif). Un lissage exponentiel peut être défini par une relation de récurrence incluant toutes les valeurs de la série chronologique observée et par un premier terme déterminé par le prévisionniste (voir le LES).
Dans leurs applications concrètes, ces relations peuvent s'écarter de la rigueur mathématique et supportent alors quelques aménagements (voir la page sur l'amortissement des obligations).
