Raisonner par récurrence forte

Lorsque l’on souhaite démontrer une propriété par récurrence sur l’entier , il arrive qu’il ne soit pas suffisant de supposer pour démontrer Hn+1 . On utilise alors la méthode suivante appelée raisonnement par récurrence forte : on choisit comme nouvelle hypothèse de récurrence

Kn : ∀k ≤ n,Hk.

Comme pour une démonstration par récurrence classique (dite “faible”), il est indispensable de respecter les points suivants :

Expliciter et nommer la propriété que l’on veut démontrer (ce choix est important car un mauvais choix peut rendre la démonstration difficile, voire impossible).
Affirmer clairement que l’on choisit la nouvelle hypothèse de récurrence
Bien vérifier l’initialisation en démontrant .
Montrer l’hérédité : on considère un entier positif quelconque et on suppose que est vraie, et on démontre alors .
Ne pas oublier la conclusion : on a alors montré que .

Exemple. Pour un entier n ≥ 2 , on souhaite montrer la propriété suivante :

“Un entier positif admet un diviseur premier”.

Pour l’initialisation à , pas de problème : 2 admet 2 comme diviseur premier.
Soit un entier. On suppose que tous les entiers admettent un diviseur premier. Si est premier, alors est vérifiée ( est son propre diviseur premier), sinon n’est pas premier et il admet alors un diviseur , avec . D’après l’hypothèse de récurrence, l’entier admet un diviseur premier qui est alors également un diviseur de .
On a donc montré que tout entier admet un diviseur premier.