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 explicitement 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.

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 Major Bac t’a concocté !

Vous pouvez aussi tester vos connaissances en mathématiques grâce à nos quiz (fonctions, suites, probabilités).

 

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.

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 un rang initial N fixé. Pour démontrer par récurrence double qu’une propriété H(n) est vraie pour tout n ≥ N, il faut :

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

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é

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

On définit la suite  par :

On souhaite démontrer que pour tout nN :

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  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 nN* :

H(n) : “.”

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

    •  donc on a bien  : H(1) est vraie.
    •  donc on a bien : H(2) est vraie.

 

Hérédité : Soit nN*. Supposons que H(n) ET H(n+1) soient vraies, et démontrons qu’alors, H(n+2) est également vraie.

Or, puisqu’on a supposé que H(n) et H(n+1) étaient vraies, on a :

Donc :

et :

Il suffit donc de démontrer que :

Or :

et par ailleurs :

Ainsi :

donc on a bien :

et donc :

Ainsi, H(n+2) est vraie.

 

Conclusion : D’après le principe de récurrence double, pour tout nN, H(n) est vraie, i.e. pour tout nN, .

 

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 un rang initial N fixé. Pour démontrer par récurrence forte qu’une propriété H(n) est vraie pour tout nN, il faut :

  1. Énoncer clairement la propriété H(n), pour tout nN.
  2. Faire l’initialisation au rang N : on démontre H(N).
  3. Démontrer l’hérédité avec une hypothèse de récurrence forte. Soit nN, on suppose que H(k) est vraie pour tout k tel que N ≤ kn, 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 forte, la propriété est vraie pour tout nN.

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

 

Un exemple rédigé

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

L’arithmétique est un domaine des mathématiques dans lequel il est souvent utile d’écrire les entiers naturels sous la forme d’un produit de nombre premiers. Par exemple, on sait que 42 = 2×3×7 (et 2, 3 et 7 sont bien des nombres premiers), ou encore que 55 = 5×11 (et 5 et 11 sont bien des nombres premiers). Pour les nombres premiers, c’est facile : ils sont directement écrits sous la forme d’un “produit d’un nombre premier” (eux-mêmes !) : 17 = 17, 29 = 29… Mais peut-on toujours écrire un entier naturel n ≥ 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 ≥ 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 ≥ 2. Supposons que H(k) soit vraie pour tout k tel que 2 ≤ kn, i.e. supposons que tout entier k tel que 2 ≤ kn puisse s’écrire comme un produit de nombre premiers. Démontrons que (n+1) peut lui aussi s’écrire comme un produit de nombres premiers.

• Soit (n+1) est premier, et 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.

• Soit (n+1) n’est pas premier, et il admet donc un diviseur m différent de 1 et de lui-même : m|(n+1). Donc il existe l tel que (n+1) = l×m, et on a nécessairement l < (n+1) et < (n+1). Donc :

Donc l’hypothèse de récurrence forte s’applique à m et l : m et l peuvent chacun s’écrire sous la forme d’un produit de nombre premiers :

où  sont des nombres premiers. Ainsi :

On a bien écrit (n+1) sous la forme d’un produit de 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 ≥ 2, H(n) est vraie, i.e. tout entier n ≥ 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é.

Poursuis ta lecture sur ces sujets

Après une prépa MPSI/MP au lycée Louis le Grand, j'ai intégré le département de Mathématiques de l'ENS de Rennes, où j'ai passé deux ans (L3 et M1).