Qu'est ce qu'un raisonnement par récurrence ?

Il y a deux phases dans le raisonnement par récurrence:

  • l'initialisation : il y a un rang n0 pour lequel ta propriété est vérifiée
  • ensuite le tout c'est de montrer que la propriété se passe d'un rang au suivant, on parle donc d'hérédité.

Ainsi si on montre que la propriété se transmet alors comme elle est vraie au rang n0, elle sera vraie au rang n0+1.

Or comme elle est vraie au rang n0+1 elle sera vérifiée au rang n0+2. ... et donc elle sera vraie pour tout n>n0.
Donc pour montrer l'hérédité, il suffit de supposer qu'a un rang n elle est vraie et de montrer que cela implique qu'elle est vraie au rang n+1.

Donc deux étapes très importantes:

  • -initialisation: vérifier que la propriété est vraie pour un rang donné.
  • -hérédité : la propriéte se transmet d'un entier à l'entier suivant.

Merci à Samuel pour cette contrib.