Pour faire un raisonnement par récurrence, il faut obligatoirement l’étape d’initialisation et celle d’hérédité. Une seule ne suffit pas.
Par exemple la proposition $Q(n)=\odq 3\text{ divise }4^n+1\cdq$ est héréditaire mais elle n’est vérifiée pour aucun entier naturel $n$…
L’étape d’initialisation se fait pour la plus petite valeur de $n$ pour laquelle la proposition est vérifiée. Cela n’est pas obligatoirement $n=0$ comme le montre l’activité préliminaire 2.
Certaines récurrences sont « doubles » c’est à dire que l’on prouve que $P(0)$ et $P(1)$ sont vraies, puis on suppose que $P(n)$ et $P(n+1)$ sont vraies pour prouver que $P(n+1)$ et $P(n+2)$ sont vraies.
On peut généraliser ce principe dans le cas où l’hypothèse de récurrence est : on suppose la propriété jusqu’à l’ordre $k$.
Ces démonstrations par récurrence sont dites fortes (celle que nous avons exposée auparavant est dite simple).
Certaines récurrences sont « descendantes » :
- Fondation : On vérifie que, pour un certain entier naturel $n_0$, $P(n_0)$ vraie.
Cela constitue l’étape d’initialisation. - Hérédité : On suppose qu’il existe un entier $k\le n_0$ tel que $P(k)$ soit vraie (hypothèse de récurrence).
On montre qu’alors que $P(k-1)$ est encore vraie. - Conclusion : Les propositions $P(0),P(1),\ldots,P(n_0)$ sont vraies.