TeoríasDetalles importantes

Nota

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$…

Nota

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.

Nota

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).

Nota

Algunas recurrencias son “descendientes”:

  1. Inicialización: Verificamos que, para un cierto entero natural $n_0$, $P(n_0)$ es verdad.
    Esto constituye la etapa de inicialización.
  2. 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.
  3. Conclusión: Las preposiciones $P(0),P(1),\ldots,P(n_0)$ son verdaderas.