Réponse : Une récurrence se déroule en 4 étapes. Prenons l'exemple suivant : tu veux prouver que n * 2 = n + n pour tout entier naturel n. (exemple très simple pour comprendre).
Explications :
D'abord on donne l'énoncé de récurrence : P(n) = "n*2 = n+n".
Ensuite on initialise, c'est a dire on vérifie si la proposition P(n) est vraie lorsque n=0. Dans notre cas, 0*2 est bien égal à 0+0, donc P(0) est vraie.
Ensuite vient l'étape d'hérédité. On suppose la proposition P(n) vraie (c'est a dire on suppose n*2 = n+n) et on regarde si on peut montrer que P(n+1) est vraie (c'est à dire que (n+1)*2 = (n+1)+(n+1)).
(n+1)*2=n*2 + 2 = n + n + 2 = n + n + 1 + 1 = (n+1)+(n+1) donc on voit que P(n+1) est vraie.
On peut enfin conclure : n*2 = n + n.
