Para hacer un razonamiento por recurrencia, es obligatorio la etapa de inicialización y la de herencia. Una sola no es suficiente.
Por ejemplo la preposición $Q(n)=\odq 3\text{ divide }4^n+1\cdq$ es hereditaria pera esta no verifica ningún entero natural $n$…
La etapa de inicialización se hace para el valor más pequeño de $n$ para el cual la preposición es verficada. Este no es obligatoriamente $n=0$ como lo muestra la actividad preliminar 2.
Algunas recurrencias son «dobles» es decir que demostramos que $P(0)$ et $P(1)$ son verdades, luego suponemos que $P(n)$ et $P(n+1)$ son verdades para demostrar que $P(n+1)$ et $P(n+2)$ son también verdades.
Podemos generalizar este principio en el caso donde la hipótesis de recurrencia es: suponemos la propiedad hasta el orden $k$.
Esta demostración por recurrencia son llamadas fuertes (las explicadas anteriormente son llamadas simples).
Algunas recurrencias son «descendientes»:
- Inicialización: Verificamos que, para un cierto entero natural $n_0$, $P(n_0)$ es verdad.
Esto constituye la etapa de inicialización. - Herencia: Suponemos que existe un entero $k\le n_0$ de manera que $P(k)$ sea verdad (hipótesis de recurrencia).
Mostramos entonces que $P(k-1)$ es todavía verdad. - Conclusión: Las preposiciones $P(0),P(1),\ldots,P(n_0)$ son verdaderas.