récurrence double et récurrence forte

Comprendre la récurrence double et la récurrence forte

Dans cet article qui fait suite à celui introduisant la démonstration par récurrence, on présente deux variantes du raisonnement par récurrence, qui peuvent s’avérer très utile dans certaines situations : la récurrence double, et la récurrence forte. Attention : ces méthodes ne sont pas au programme du lycée ! Cet article s’adresse donc plutôt aux élèves déjà à l’aise avec le principe de démonstration par récurrence, et/ou qui envisagent de s’orienter dans des études à dominante mathématique après le Bac (et qui souhaitent donc prendre de l’avance pour approfondir le programme de mathématiques post-bac).

Avant de te plonger dans la lecture de cet article, on t’invite à revoir les bases de la démonstration par récurrence grâce à cet autre article que l’on t’a concocté !

Principe et méthodologie de la récurrence double

Intuitivement, une propriété que l’on démontre par récurrence est une propriété dont la véracité se “propage” d’un rang à l’autre. On commence donc par démontrer qu’elle est vraie quelque part (à l’étape d’initialisation, à un rang \(n\) ), puis on démontre que si elle est vraie à un rang quelconque \(n\), alors elle l’est aussi au rang suivant (c’est l’étape d’hérédité : la véracité de la propriété se “propage” du rang \(n\) au rang suivant, \(n+1\)). Ceci permet de conclure qu’une telle propriété est vraie pour tous les rangs supérieurs ou égaux au rang d’initialisation (logique car si ça fonctionne pour un rang en particulier que l’on a choisi et fixé au hasard, alors forcément ça fonctionnera pour n’importe quel rang plus généralement).

La récurrence double est une généralisation assez naturelle de ce procédé. Elle permet en effet de démontrer des propriétés dont la véracité ne se “propage” pas directement d’un rang au rang suivant (comme dans la démonstration par récurrence classique), mais dont la véracité à un rang donné dépend de sa véracité aux deux rangs précédents.

Formellement, ceci requiert deux modifications par rapport à une démonstration par récurrence classique (l’une à l’étape d’initialisation, l’autre à l’étape d’hérédité). La méthodologie d’une démonstration par récurrence double est en effet la 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 double que, pour tout  \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\), la propriété H(\(n\)) est vraie , il faut :

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

 

Attention : la double initialisation est importante ! En effet, intuitivement, pour dire que H(\(n+2\)) est vraie, on a besoin d’avoir démontré que H(\(n\)) et H(\(n+1\)) étaient bien vraies (et on peut ensuite démontrer que H(\(n+3\)) est vraie, puisqu’on a démontré H(\(n+1\)) et H(\(n+2\)), puis on peut démontrer que H(\(n+4\)) est vraie etc. : c’est ce que formalise l’hérédité).

Un exemple rédigé pour comprendre la récurrence simple

Illustrons l’utilité du principe de récurrence double grâce à un exemple.

On définit la suite \((a_{n})\) par :

\( \begin{cases} a_{0}=a_{1}=1 \\ \forall n \in \mathbb{N}, a_{n+2}=a_{n+1}+\frac{2}{n+2}a_{n} \end{cases}  \)

 

On souhaite démontrer que pour tout \(n \in \mathbb{N}^*\) : \(1 \leq a_{n} \leq n^2 \)

On va utiliser pour cela une récurrence double. En effet, il semble cohérent d’utiliser un tel procédé de démonstration, car la suite \((a_{n})\) est une suite récurrente d’ordre 2 : on connait ses deux premiers termes, et on sait que chacun des termes de la suite de rang ≥ 2 est déterminé par les deux termes précédents (ce qui permettra d’exploiter l’hypothèse de récurrence double, à l’étape d’hérédité) !

Notons donc, pour tout \(n \in \mathbb{N}^*\), H(\(n\)) : “\(1 \leq a_{n} \leq n^2 \)”

Double initialisation : vérifions que H(1) ET H(2) sont vraies.

on a \(a_{1}=1 \), donc \(1 \leq a_{1} \leq 1^2 \)

donc on a bien : H(1) vraie.

De plus, on a  \(a_{2}=a_{1}+\frac{2}{2}a_{0} \), donc

\(a_{2}=2 \), donc

\(1 \leq a_{2} \leq 2^2 \)

donc on a bien : H(2) vraie.

Hérédité : Soit \(n \in \mathbb{N}^*\). Supposons que H(\(n\)) et H(\(n+1\)) soient vraies, et démontrons qu’alors, H(\(n+2\)) est également vraie.

D’après les hypothèses de récurrence,  on a :

\( \begin{cases} 1 \leq a_{n} \leq n^2 \: ① \\ 1 \leq a_{n+1} \leq (n+1)^2 \: ② \end{cases}  \)

et on a \(a_{n+2}=a_{n+1}+\frac{2}{n+2}a_{n}\)

donc en multipliant \( \frac{2}{n+2} \geq 0 \) dans l’inégalité ①, on a :

\( \frac{2}{n+2} \leq \frac{2}{n+2}a_{n} \leq \frac{2n^2}{n+2} \: ③ \), et en additionnant membre à membre les inégalités ② et ③, on a :

\( \frac{2}{n+2} + 1 \leq a_{n+2} \leq \frac{2n^2}{n+2} + (n+1)^2 \), et comme \( \frac{2}{n+2} \geq 0 \) :

\( 1 \leq a_{n+2} \leq \frac{2n^2}{n+2} + n^2+4n+2-2n-1\), d’où :

\( 1 \leq a_{n+2} \leq (n+2)^2+2n(\frac{n}{n+2}-1)-1 \), ie.

\( 1 \leq a_{n+2} \leq (n+2)^2-\frac{4n}{n+2}-1 \), donc :

\( 1 \leq a_{n+2} \leq (n+2)^2-\frac{5n+2}{n+2} \), et comme \( -\frac{5n+2}{n+2} \leq 0 \) :

\( 1 \leq a_{n+2} \leq (n+2)^2 \)

Ainsi, H(\(n+2\)) est vraie.

Conclusion : D’après le principe de récurrence double, pour tout \(n \in \mathbb{N}^*\), H(\(n\)) est vraie

Cet exemple illustre bien l’intérêt d’une récurrence double par rapport à une récurrence classique : étant donné que chaque terme de rang supérieur ou égal à 2 de la suite dépend des deux termes précédents de la suite, il est bien nécessaire d’avoir une hypothèse de récurrence portant sur les deux termes précédents (et non pas uniquement le terme précédent), pour pouvoirs tirer des conclusions intéressantes sur la suite étudiée.

 

Principe et méthodologie de la récurrence forte

On a vu que la récurrence classique permet de démontrer des propriétés dont la véracité se “propage” d’un rang au rang suivant, et que la récurrence double permet de démontrer des propriétés dont la véracité à un rang donné est impliquée par sa véracité aux deux rangs précédents. La récurrence forte, elle, va permettre de démontrer des propriétés dont la véracité à un rang donné dépend de la véracité à tous les rangs précédents.

Formellement, la différence entre la démonstration par récurrence classique et la démonstration par récurrence forte réside exclusivement dans l’étape d’hérédité. La méthodologie de démonstration est en effet la 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 forte que, pour tout  \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\), la propriété H(\(n\)) est vraie , 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 forte. Soit \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\) (on fixe un entier au hasard quelconque dans l’ensemble en question), Supposons que H(\(n_0\)), H(\(n_0+1\)), …,H(\(n\)) sont vraies (ie. pour tout \({\displaystyle k \in }\) \([\![n_{0};n]\!]\), H(\(k\)) 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 forte, pour tout  \({\displaystyle n \in }\) \([\![n_{0};+\infty[\![\) la propriété H(\(n\)) est vraie“.

Soulignons que, contrairement à ce qu’il se passe pour la récurrence double, une récurrence forte ne requiert qu’une initialisation simple (on ne démontre que H(\(n_{0}\))).

Un exemple rédigé pour comprendre la récurrence forte

Illustrons sur un exemple l’utilité d’une telle méthode de démonstration.

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 \)

Rappel sur les nombres premiers

L’égalité n = n × 1 nous montre que tout entier naturel supérieur à 1 a au moins deux diviseurs : 1 et lui même. (en effet, on peut très bien écrire : \(1= \frac{n}{n} \) ou \( n= \frac{n}{1}) \) Les nombres premiers sont les nombres qui n’ont pas d’autres diviseurs.

Un nombre premier est un entier naturel qui a exactement deux diviseurs : 1 et lui même.

Exemples :

    • 2, 3, 5, 7, 11 sont des nombres premiers
    • 4 n’est pas un nombre premier car il a trois diviseurs : 1, 4 et 2
    • 1 n’est pas un nombre premier car il n’a qu’un seul diviseur : 1

Mais peut-on toujours écrire un entier naturel \(n \geq 2 \) sous la forme d’un produit de nombres premiers ? La réponse est oui, et on va le démontrer par récurrence forte.

Notons donc, pour tout  \(n \geq 2 \) : H(\(n\)) : “L’entier \(n\) peut s’écrire sous la forme d’un produit de nombres premiers.”

Initialisation : Vérifions que H(2) est vraie.

2 est un nombre premier, donc il s’écrit bien comme produit d’un nombre premier (lui-même). H(2) est donc bien vraie.

Hérédité : Soit \(n \geq 2 \). Supposons que pour tout \({\displaystyle k \in }\) \([\![2;n]\!]\), H(\(k\)) est vraie, i.e. supposons que tout \({\displaystyle k \in }\) \([\![2;n]\!]\) \(k\) peut s’écrire comme un produit de nombre premiers. Démontrons alors que \(n+1\) peut lui aussi s’écrire comme un produit de nombres premiers.

Deux cas se présentent :

Si \(n+1\) est un nombre premier, alors il peut bien s’écrire comme un produit d’un nombre premier (lui-même). Dans ce cas, H(\(n+1\)) est bien vraie.

Si \(n+1\) n’est pas premier, alors il existe (au moins un) diviseur \(m\) (entier naturel non nul) tel que :

\( \begin{cases} m \neq 1 \\ m \neq (n+1) \\ \exists l \in \mathbb{N}, n+1=l \times m \end{cases}  \)

Or, comme tout diviseur \(m\) d’un entier \(n+1\) est compris entre 1 et \(n+1\) (en effet, pour qu’un entier en divise un autre, il faut nécessairement qu’il soit strictement plus grand que 0 et plus petit que lui), on a : \( 1 \leq m \leq n+1\)

or comme on a \(m \neq 1 \) et \( m \neq (n+1)\), on en déduit que : \({\displaystyle m \in }\) \([\![2;n]\!]\)

Et comme \( m \in [\![2;n]\!]\) et comme, d’après l’hypothèse de récurrence, on sait que pour tout \({\displaystyle k \in }\) \([\![2;n]\!]\), \(k\) peut s’écrire comme un produit de nombres premiers, on peut poser en particulier \(k=m\)

Donc \(m\) peut s’écrire comme un produit de nombres premiers

De plus, on a :

\( 2 \leq m \leq n \), d’où en composant par la fonction inverse décroissante sur \( \mathbb{R^{*}_{+}} \) :

\( \frac{1}{n} \leq \frac{1}{m} \leq \frac{1}{2} \), d’où :

\( \frac{n+1}{n} \leq \frac{n+1}{m} \leq \frac{n+1}{2} \), or comme \(  \frac{n+1}{2} \leq n+1 \)

\( 1 + \frac{1}{n} \leq \frac{n+1}{m} \leq n+1 \) et comme \(  0 \leq \frac{1}{n} \), et \(l=\frac{n+1}{m}\)

\( 1  \leq l \leq n+1 \)

Supposons alors que \(l=n+1\)

comme \(n+1=l.m\), on peut écrire que \(n+1=(n+1).m\), donc que \(m=1\)

ce qui est absurde comme on sait que \(m \neq 1 \)

donc \(l \neq n+1\)

On montre de même que \(l \neq 1\)

ainsi, on peut écrire que \( 2  \leq l \leq n \)

donc comme \( l \in [\![2;n]\!]\) et comme, d’après l’hypothèse de récurrence, on sait que pour tout \({\displaystyle k \in }\) \([\![2;n]\!]\), \(k\) peut s’écrire comme un produit de nombres premiers, on peut poser en particulier \(k=l\)

Donc \(l\) peut s’écrire comme un produit de nombres premiers

 

Ainsi, comme \(m\) et \(l\) sont deux nombres premiers et comme on a \(n+1=l.m\), on peut en conclure que \(n+1\) s’écrit comme le produit de deux nombres premiers.

Donc dans ce cas également, H(\(n+1\)) est bien vraie.

⇒ Ainsi, dans tous les cas, H(\(n+1\))est vraie.

Conclusion : D’après le principe de récurrence forte, pour tout  \(n \geq 2 \) H(\(n\)) est vraie, i.e. tout entier \(n \geq 2\) peut s’écrire sous la forme d’un produit de nombres premiers.

Si l’on avait essayé de démontrer cette propriété avec une récurrence classique, on n’aurait pas réussi à aboutir (essaie de le faire, pour te rendre compte par toi-même que ce n’est pas possible) ! L’astuce, à l’étape d’hérédité, réside vraiment dans le fait que, comme on suppose H(\(k\)) vraie pour tous les rangs \(k\) compris entre 2 et \(n\), on peut ensuite l’appliquer à \(l\) et \(m\) (les diviseurs de \(n+1\)), même si on ne sait pas explicitement qui ils sont : il suffit de savoir que ce sont des entiers compris entre 2 et \(n\). Si on supposait seulement H(\(n\)) vraie, on ne pourrait rien dire a priori sur \(l\) et \(m\) !

Ceci illustre bien la puissance d’un raisonnement par récurrence forte, par rapport à une récurrence classique. Et la bonne nouvelle, c’est que si le raisonnement par récurrence forte est plus difficile à comprendre que le raisonnement par récurrence classique, il n’est en revanche pas beaucoup plus compliqué à rédiger ! Les étapes se ressemblent beaucoup (énoncé de la propriété à démontrer, initialisation simple, hérédité et conclusion), et il faut seulement garder en tête que, lorsque l’on travaille sur l’étape d’hérédité et que l’on veut démontrer la propriété au rang \(n+1\), on suppose la propriété vraie à tous les rangs précédant \(n\), et non plus seulement au rang \(n\), ce qui donne plus de marge de manœuvre dans la démonstration.

A lire également : réviser les maths de manière ludique avec la télé réalité.