récurrence double et récurrence forte

La démonstration par récurrence

Ah, la démonstration par récurrence ! Elle a fait pâlir plus d’un élève de lycée… Et pourtant, ce principe de démonstration est assez intuitif, et surtout facile à appliquer, une fois bien compris. Reprenons donc depuis le début.

 

La démonstration par récurrence, ou le principe des dominos

Oublions un instant le formalisme mathématique, et revenons à une dimension plus “manuelle”.

Imaginons un axe sur lequel seraient alignés une infinité de dominos, posés verticalement. Numérotons ces dominos dans l’ordre : 0, 1, 2, 3 etc. L’objectif est de faire tomber tous les dominos.

Pour cela, il faut que deux conditions soient réunies :

  1. Les dominos doivent être placés suffisamment près les uns des autres, de sorte que si le domino numéro \(n\) tombe, alors le domino suivant (le numéro \(n+1\)) tombe également.
  2. Il faut faire tomber le domino numéro 0 (sinon il ne se passe rien du tout…) !

Si ces deux conditions sont réunies, alors c’est gagné : tous les dominos tombent !

Intuitif, non ? Eh bien il s’agit exactement du principe de la démonstration par récurrence. Essayons de le comprendre en reformulant cet exemple des dominos en termes mathématiques.

La démonstration par récurrence sert à démontrer des propriétés qui portent sur les entiers naturels, c’est-à-dire des propriétés de la forme : “Pour tout \(n \in \mathbb{N}\), blablabla” . Dans notre exemple ci-dessus, la propriété à démontrer serait : “Pour tout \(n \in \mathbb{N}\), le domino numéro \(n\) tombe.” .

On note H(\(n\)) une telle propriété au rang \(n\). Dans notre exemple, on aurait donc :

H(\(n\)) : “Le domino numéro \(n\) tombe.”

La démonstration par récurrence consiste :

  1. D’abord, à vérifier que la propriété est vraie au rang 0 (i.e. on vérifie que H(0) est vraie). Dans notre exemple des dominos, cela revient à vérifier que le premier domino (le domino numéro 0) tombe. Cette étape s’appelle l’initialisation.
  2. Ensuite, à vérifier que si la propriété est vraie à un rang \(n\), alors elle sera aussi vraie au rang \(n+1\) (i.e. on vérifie que si H(\(n\)) est vraie, alors H(\(n+1\)) est aussi vraie). Dans notre exemple, cela revient à constater que, si le domino numéro \(n\) tombe, comme la distance entre les dominos est suffisamment petite, alors le domino numéro \(n+1\) tombe également. Cette étape s’appelle l’hérédité.

Si ces deux étapes sont vérifiées, alors la propriété sera vraie pour tous les entiers naturels (on aura démontré que pour tout \(n \in \mathbb{N}\), H(\(n\)) est vraie). Dans notre exemple, cela revient à dire que tous les dominos tombent (car pour tout \(n \in \mathbb{N}\), le domino numéro \(n\) tombe). C’est la conclusion du raisonnement par récurrence.

 

Méthodologie : rédiger efficacement une démonstration par récurrence

Il faut penser à tenter une démonstration par récurrence lorsqu’on est en présence d’une propriété qui se “propage” de proche en proche sur les entiers naturels (comme la chute de nos dominos…). Toutefois, il n’est pas toujours facile d’identifier de telles propriétés… Il faut donc toujours avoir en tête que l’on dispose de la démonstration par récurrence dans notre “boite à outils mathématiques”, et envisager de l’utiliser si l’on nous demande de démontrer une propriété portant sur les entiers naturels qui ne nous semble pas facile à prouver de manière “directe”.

Une fois identifiée une démonstration à faire par récurrence, il faut :

  1. Énoncer clairement la propriété H(\(n\)) pour tout \(n \in \mathbb{N}\).
  2. Faire l’initialisation : on démontre H(0).
  3. Démontrer l’hérédité. Soit \(n \in \mathbb{N}\), on suppose que H(\(n\)) est vraie, et on en déduit que H(\(n+1\)) est vraie.
  4. Conclure avec une phrase du type : “D’après le principe de récurrence, la propriété est vraie pour tout \(n \in \mathbb{N}\)”.

 

À toi de jouer !

Exercice 1 sur la démonstration par récurrence classique

On définit la suite \((u_n)\) par :

\(\begin{cases} u_{0}=3 \\ \forall n \in \mathbb{N}, u_{n+1}=4u_{n} \end{cases}\)

Démontrer que : \(\forall n \in \mathbb{N}, u_{n}=4^n \times 3 \)

Correction de l’exercice 1

On pose pour tout \(n \in \mathbb{N} \) H(\(n\) : “\(u_{n}=4^n \times 3 \)”

Initialisation : pour \(n=0\)

on a \(u_{0}=3=4^{0} \times 3\)

Donc H(0) est vérifiée

Hérédité : Soit \(n \in \mathbb{N} \). Supposons que H(\(n\)) est vraie. Montrons alors que : \(u_{n+1}=4^{n+1} \times 3 \)

On peut écrire :

\(u_{n+1}=4\times u_{n}\), d’où d’après l’hypothèse de récurrence :

\(u_{n+1}=4\times 4^n \times 3\), ie.

\(u_{n+1}=4^{n+1} \times 3\)

Donc H(\(n+1\)) est vraie.

Conclusion : Par principe de récurrence, on a : \(\forall n \in \mathbb{N}, u_{n}=4^n \times 3 \)

 

Exercice 2 sur une démonstration par récurrence un peu plus poussée

Démontrer que pour tout \(n \in \mathbb{N}, 2^{2n}+2\) est un entier divisible par 3.

Rappel sur les diviseurs

Un entier naturel \(b\) est un diviseur de l’entier naturel \(a\) lorsque le reste de la division euclidienne de \(a\) par \(b\) est égal à 0. Donc : \( \exists q \in \mathbb{N}, \ a = b.q \)

 

Correction de l’exercice 2

On pose pour tout \(n \in \mathbb{N} \), H(\(n\)) : “\(2^{2n}+2\) est un entier divisible par 3”

Initialisation : pour \(n=0\)

On a \(2^{2} \times 0+2 =1+2=3\), or \(3=3 \times 1\), donc en posant \(q=1\)
\(\exists q \in \mathbb{N}\), \(3 = 3.q\), donc par définition, 3 est bien divisible par 3.
Donc \(2^{2 \times 0}+2\) est bien un entier divisible par 3

Donc H(0) est vérifiée.

Hérédité : Soit \(n \in \mathbb{N} \). Supposons que H(\(n\)) est vraie. Montrons alors que : \(2^{2(n+1)}+2\) est un entier divisible par 3

On a :

\(2^{2(n+1)}+2=2^{2n+2)}+2 \)

\(\qquad \qquad=2^{2n} \times 2^{2}+2 \)

\(\qquad \qquad=2^{2n} \times 4+2\)

\(\qquad \qquad=2^{2n} \times 3+2^{2n}+2\)

\(\qquad \qquad=(2^{2n} \times 3)+(2^{2n}+2)\)

Or en posant \(l=2^{2n}\), on peut écrire :

\(\exists l \in \mathbb{N}, 2^{2n} \times 3 = 3.l\), donc par définition, \(2^{2n} \times 3\) est un entier divisible par 3

Comme en outre, d’après l’hypothèse de récurrence, \(2^{2n}+2\) est un entier divisible par 3, alors par définition :

\(\exists k \in \mathbb{N}, 2^{2n}+2 = 3.k\), d’où :

\(2^{2(n+1)}+2=3l+3k \), donc :

\(\qquad \qquad=3(l+k) \), et en posant \(m=l+k\), on peut écrire :

\(\exists m \in \mathbb{N}, 2^{2(n+1)}+2= 3.m\)

Donc par définition, \(2^{2(n+1)}+2\) est un entier divisible par 3.

Ainsi, H(\(n+1\)) est vérifiée.

Conclusion : Par principe de récurrence, on a, pour tout \(n \in \mathbb{N}\), \(2^{2n}+2\) qui est un entier divisible par 3

 

 

Pour aller un peu plus loin : la récurrence “à partir d’un certain rang”

Si tu as bien compris les deux premiers paragraphes de cet article et si tu as réussi à faire les deux exercices du paragraphe ci-dessus, tu es armé·e pour répondre à l’essentiel des questions que l’on pourrait te poser autour de la démonstration par récurrence.

Cependant, ce principe de démonstration peut être légèrement adapté pour démontrer des propriétés non plus sur l’ensemble des entiers naturels, mais à partir d’un certain rang seulement. Mais le principe est exactement le même, comme tu vas vite le comprendre en reprenant notre exemple des dominos.

Imaginons en effet que l’on ne souhaite plus faire tomber tous les dominos, mais seulement les dominos dont les numéros sont supérieurs ou égaux à 11. Facile, non ? Il suffit que :

  1. Les dominos dont les numéros sont supérieurs ou égaux à 11 soient placés suffisamment près les uns des autres, de sorte que si le domino numéro n tombe, alors le domino suivant (le numéro n+1) tombe également, pour n ≥ 11.
  2. On fasse tomber le domino numéro 11 (et non plus le domino numéro 0) !

Si ces deux conditions sont réunies, alors c’est gagné : tous les dominos dont les numéros sont supérieurs ou égaux à 11 tombent !

Si l’on formalise ceci mathématiquement on obtient la méthodologie suivante.

Soit \(n_{0} \in \mathbb{Z}\) et une propriété à montrer sur l’ensemble des entiers compris entre le premier terme \(n_{0}\) et \({\displaystyle +\infty }\) (on note cet ensemble : \([\![n_{0};+\infty[\![\))

Pour démontrer par récurrence que, pour tout  \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\), la propriété H(\(n\)) est vraie à partir d’un certain rang  qu’on notera \(n_{0}\) , il faut :

  1. Énoncer clairement , pour tout  \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\) la propriété H(\(n\)).
  2. Faire une l’initialisation au rang \(n_{0}\) : on démontre que la propriété est vérifiée au rang \(n_{0}\) (ie. on montre que H(\(n_{0}\)) est vraie).
  3. Démontrer l’hérédité avec une hypothèse de récurrence. Soit \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\) (on fixe un entier au hasard quelconque dans l’ensemble en question), Supposons que H(\(n\)) est vraie . On s’arrange par la suite pour montrer que H(\(n+1\)) est vraie.
  4. Conclure avec une phrase du type : “Par principe de récurrence, pour tout  \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\) la propriété H(\(n\)) est vraie“.

Encore à toi de jouer !

Exercice 3

Démontrer que : \(\forall n \in [\![6;+\infty[\![, 6n+7 \leq 2^n \)

 

Correction de l’exercice 3

On pose pour tout \(n \geq 6\), H(\(n\)) : “\(6n+7 \leq 2^n \)”

Initialisation : pour \(n=6\)

On a \(6 \times 6 +7 = 43\)

et \(2^6=64\)

donc on a bien \(6 \times 6 +7 \leq 2^6\)

Donc H(6) est vérifiée.

Hérédité : Soit \(n \geq 6\). Supposons que H(\(n\)) est vraie. Montrons alors que : \(6(n+1)+7 \leq 2^{(n+1)} \)

On a, d’après l’hypothèse de récurrence :

\(6n+7 \leq 2^n\), d’où en multipliant par 2 :

\(2(6n+7) \leq 2^{(n+1)}\)

\(12n+14 \leq 2^{(n+1)}\)

or \(6(n+1)+7=6n + 13\) et on a bien \(6n + 13 \leq 12n+14\), donc :

\(6(n+1)+7 \leq 2^{(n+1)}\)

Donc H(\(n+1\)) est vérifiée.

Conclusion : Par principe de récurrence, on a, \( \forall n \in [\![6;+\infty[\![, \; 6n+7 \leq 2^n \)

 

 

Te voilà maintenant armé·e pour affronter tous les exercices de niveau Bac nécessitant une démonstration par récurrence ! Si tu veux aller plus loin et aborder les concepts de récurrence double et de récurrence forte (qui ne sont pas explicitement au programme de lycée, mais qui constituent des notions mathématiques importantes abordées dans les études supérieures scientifiques), on t’explique ces deux concepts dans cet autre article. Mais si tu préfères pour le moment te concentrer sur les exercices de niveau Bac, la bonne compréhension et la maitrise des notions abordées dans l’article que tu viens de lire sont amplement suffisantes !

Pour aller plus loin : les autres types de raisonnements par récurrence.