1 – Principe du raisonnement par récurrence
• En mathématiques, on doit souvent démontrer qu'une propriété \(P_{n}\) est vraie pour tout entier naturel \(n\).
Par exemple : « Pour tout entier \(n \geq 1\), \(1 + 2 + \ldots + n = \dfrac{n(n + 1)}{2}\) ».
• On ne peut pas vérifier cette propriété pour chaque valeur de \(n\) (il y en a une infinité).
Le raisonnement par récurrence permet de la démontrer en deux étapes.
Par exemple : « Pour tout entier \(n \geq 1\), \(1 + 2 + \ldots + n = \dfrac{n(n + 1)}{2}\) ».
• On ne peut pas vérifier cette propriété pour chaque valeur de \(n\) (il y en a une infinité).
Le raisonnement par récurrence permet de la démontrer en deux étapes.
Théorème (Principe de récurrence) : Soit \(\left( P_{n} \right)\) une propriété dépendant d'un entier naturel \(n\). Si :
• Initialisation : la propriété \(P_{0}\) est vraie ;
• Hérédité : pour tout entier \(n \geq 0\), si \(P_{n}\) est vraie alors \(P_{n + 1}\) est vraie ;
alors la propriété \(P_{n}\) est vraie pour tout entier naturel \(n\).
• Initialisation : la propriété \(P_{0}\) est vraie ;
• Hérédité : pour tout entier \(n \geq 0\), si \(P_{n}\) est vraie alors \(P_{n + 1}\) est vraie ;
alors la propriété \(P_{n}\) est vraie pour tout entier naturel \(n\).
Remarques :
• Les 2 étapes (initialisation et hérédité) sont indispensables. L'une sans l'autre ne permet pas de conclure.
• Pour l'hérédité, on suppose \(P_{n}\) vraie (c'est l'hypothèse de récurrence) et on démontre que \(P_{n + 1}\) est vraie.
• La récurrence peut démarrer à un rang \(n_{0} \geq 0\). La propriété est alors démontrée pour tout \(n \geq n_{0}\).
• Les 2 étapes (initialisation et hérédité) sont indispensables. L'une sans l'autre ne permet pas de conclure.
• Pour l'hérédité, on suppose \(P_{n}\) vraie (c'est l'hypothèse de récurrence) et on démontre que \(P_{n + 1}\) est vraie.
• La récurrence peut démarrer à un rang \(n_{0} \geq 0\). La propriété est alors démontrée pour tout \(n \geq n_{0}\).
Méthode : La rédaction d'une récurrence suit toujours le plan suivant :
1. Énoncer la propriété \(P_{n}\) à démontrer.
2. Initialisation : Vérifier que \(P_{0}\) (ou \(P_{n_{0}}\)) est vraie.
3. Hérédité : On fixe \(n\), on suppose \(P_{n}\) vraie et on démontre \(P_{n + 1}\).
4. Conclusion : Par le principe de récurrence, \(P_{n}\) est vraie pour tout \(n \in \mathbb{N}\).
1. Énoncer la propriété \(P_{n}\) à démontrer.
2. Initialisation : Vérifier que \(P_{0}\) (ou \(P_{n_{0}}\)) est vraie.
3. Hérédité : On fixe \(n\), on suppose \(P_{n}\) vraie et on démontre \(P_{n + 1}\).
4. Conclusion : Par le principe de récurrence, \(P_{n}\) est vraie pour tout \(n \in \mathbb{N}\).
2 – Exemples d'application
Exemple 1 :
Démontrer que pour tout entier \(n \geq 1\) : \(1 + 2 + 3 + \ldots + n = \dfrac{n(n + 1)}{2}\).
• Énoncé : Soit la propriété \(P_{n}\) : « \(1 + 2 + \ldots + n = \dfrac{n(n + 1)}{2}\) ». Montrons que pour tout \(n \geq 1\), \(P_{n}\) est vraie.
• Initialisation : Pour \(n = 1\) : à gauche \(1\) ; à droite \(\dfrac{1 \times 2}{2} = 1\). Donc \(P_{1}\) est vraie.
• Hérédité : Soit \(n \geq 1\) fixé. On suppose \(P_{n}\) vraie, c'est-à-dire \(1 + 2 + \ldots + n = \dfrac{n(n + 1)}{2}\).
On doit alors montrer \(P_{n + 1}\), c'est-à-dire \(1 + 2 + \ldots + n + (n + 1) = \dfrac{(n + 1)(n + 2)}{2}\).
Or : \(1 + 2 + \ldots + n + (n + 1) = \dfrac{n(n + 1)}{2} + (n + 1)\) (par hypothèse de récurrence) \[= \dfrac{n(n + 1)}{2} + \dfrac{2(n + 1)}{2} = \dfrac{(n + 1)(n + 2)}{2} \quad \text{(factorisation par } n + 1\text{)}\] • Conclusion : \(P_{1}\) est vraie et sous l'hypothèse \(P_{n}\), \(P_{n + 1}\) est vraie.
Par le principe de récurrence, pour tout \(n \geq 1\), \(P_{n}\) est vraie. □
Exemple 2 (Inégalité de Bernoulli) :
Démontrer que pour tout \(a > -1\) et tout \(n \in \mathbb{N}\) : \((1 + a)^{n} \geq 1 + na\).
• Énoncé : Soit un réel \(a > -1\). Montrons que pour tout \(n \in \mathbb{N}\), la propriété \(P_{n}\) : « \((1 + a)^{n} \geq 1 + na\) » est vraie.
• Initialisation : Pour \(n = 0\) : à gauche \((1 + a)^{0} = 1\) ; à droite \(1 + 0 \times a = 1\). On a bien \(1 \geq 1\). Donc \(P_{0}\) est vraie.
• Hérédité : Soit \(n \geq 0\) fixé. On suppose \(P_{n}\) vraie, c'est-à-dire \(P_{n}\) : « \((1 + a)^{n} \geq 1 + na\) ».
On doit alors montrer \(P_{n + 1}\), c'est-à-dire \((1 + a)^{n + 1} \geq 1 + (n + 1)a\).
Par hypothèse de récurrence on a \((1 + a)^{n} \geq 1 + na\). Multiplions les deux membres de l'inégalité par \((1 + a)\).
Comme \(a > -1\), on a \(1 + a > 0\) : l'inégalité ne change pas de sens et on obtient donc : \[(1 + a)^{n} \times (1 + a) \geq (1 + na)(1 + a)\] D'où \((1 + a)^{n + 1} \geq 1 + a + na + na^{2} = 1 + (n + 1)a + na^{2}\).
Puis, \((1 + a)^{n + 1} \geq 1 + (n + 1)a\) (car \(na^{2} \geq 0\) : un produit de deux nombres positifs).
Ce qui montre que \(P_{n + 1}\) est vraie.
• Conclusion : \(P_{0}\) est vraie et sous l'hypothèse \(P_{n}\), \(P_{n + 1}\) est vraie.
Par le principe de récurrence, pour tout \(n \in \mathbb{N}\), \(P_{n}\) est vraie. □
Point de vigilance : multiplier une inégalité par un nombre n'en conserve le sens que si ce nombre est positif. C'est exactement là qu'intervient l'hypothèse \(a > -1\) : il faut la citer au moment où l'on multiplie, sinon la démonstration est incomplète.
Exemple 3 :
Soit \(\left( u_{n} \right)\) définie par \(u_{0} = 2\) et \(u_{n + 1} = \dfrac{1 + u_{n}}{2}\). Montrer que pour tout \(n \in \mathbb{N}\), \(u_{n} \geq 1\).
• Énoncé : Soit la propriété \(P_{n}\) : « \(u_{n} \geq 1\) ». Montrons que pour tout \(n \in \mathbb{N}\), \(P_{n}\) est vraie.
• Initialisation : Pour \(n = 0\) : \(u_{0} = 2\) et \(2 \geq 1\). Donc \(P_{0}\) est vraie.
• Hérédité : Soit \(n \geq 0\) fixé. On suppose \(P_{n}\) vraie, c'est-à-dire \(u_{n} \geq 1\).
On doit alors montrer \(P_{n + 1}\), c'est-à-dire \(u_{n + 1} \geq 1\), autrement dit \(\dfrac{1 + u_{n}}{2} \geq 1\).
Or : \(u_{n} \geq 1\) (par hypothèse de récurrence)
donc \(1 + u_{n} \geq 2\) (on ajoute \(1\) aux deux membres)
donc \(\dfrac{1 + u_{n}}{2} \geq \dfrac{2}{2} = 1\) (on divise par \(2 > 0\) : le sens de l'inégalité est conservé)
c'est-à-dire \(u_{n + 1} \geq 1\) : \(P_{n + 1}\) est vraie.
• Conclusion : \(P_{0}\) est vraie et sous l'hypothèse \(P_{n}\), \(P_{n + 1}\) est vraie.
Par le principe de récurrence, pour tout \(n \in \mathbb{N}\), \(P_{n}\) est vraie. □
Remarque (méthode avec la fonction \(f\)) : on pose \(f(x) = \dfrac{1 + x}{2}\), de sorte que \(u_{n + 1} = f\left( u_{n} \right)\).
La fonction \(f\) est croissante sur \(\mathbb{R}\) (fonction affine de coefficient \(\dfrac{1}{2} > 0\)).
Or, une fonction est croissante sur \(I\) si pour tous \(x\), \(y\) de \(I\) : \(x \leq y\) (antécédents) \(\Rightarrow f(x) \leq f(y)\) (images).
Si \(u_{n} \geq 1\) (hypothèse de récurrence), alors \(f\left( u_{n} \right) \geq f(1)\), et donc \(u_{n + 1} \geq 1\) (car \(u_{n + 1} = f\left( u_{n} \right)\) et \(f(1) = 1\)).
Cette rédaction est à retenir pour toutes les suites du type \(u_{n + 1} = f\left( u_{n} \right)\) : elle sert aussi à démontrer le sens de variation (voir fiche A1.2).
La fonction \(f\) est croissante sur \(\mathbb{R}\) (fonction affine de coefficient \(\dfrac{1}{2} > 0\)).
Or, une fonction est croissante sur \(I\) si pour tous \(x\), \(y\) de \(I\) : \(x \leq y\) (antécédents) \(\Rightarrow f(x) \leq f(y)\) (images).
Si \(u_{n} \geq 1\) (hypothèse de récurrence), alors \(f\left( u_{n} \right) \geq f(1)\), et donc \(u_{n + 1} \geq 1\) (car \(u_{n + 1} = f\left( u_{n} \right)\) et \(f(1) = 1\)).
Cette rédaction est à retenir pour toutes les suites du type \(u_{n + 1} = f\left( u_{n} \right)\) : elle sert aussi à démontrer le sens de variation (voir fiche A1.2).
