Raisonnement par récurrence

Principe de la démonstration par récurrence

Soit une propriété dépendant d'un entier naturel .
Pour montrer que est vraie pour tout () on peut utiliser le raisonnement par récurrence qui se pratique en 2 étapes :
(i) Initialisation : On montre que est vraie, c'est à dire que la propriété est vraie pour l'entier .
(ii) Hérédité : On suppose que la propriété est vraie pour un certain entier et on montre qu'alors elle est vraie pour l'entier suivant .
Lorsque la propriété est initialisée et héréditaire, on peut conclure que est vraie pour tout .

 

 

Exemple

La suite est définie par et pour tout entier naturel:
Démontrer par récurrence, que la suite est bornée par et 5.
La propriété à montrer pour tout entier est : « ».
Initialisation
, ainsi
Donc est vraie.
Hérédité
On suppose que la propriété est vraie à un certain rang , on a donc l'hypothèse de récurrence :
On montre qu'alors la propriété est vraie au rang .
On part de l'hypothèse de récurrence :
On remarque que , où est la fonction affine définie par .
Cette fonction est décroissante sur , donc on peut l'appliquer à l'inégalité de l'hypothèse de récurrence en changeant les sens des inégalités ce qui donne :
soit
comme , on a finalement .
Donc est vraie.
Ainsi la propriété est vraie au rang et elle est héréditaire donc selon le principe de récurrence la propriété est vraie pour tout entier .

 

A voir aussi