2.3. Ecuaciones de recurrencia.
En general, las ecuaciones de recurrencia tienen la forma:
t(n) = b Para 0 ? n ? n0 Casos base
t(n) = f (t(n), t(n-1), ..., t(n-k), n) En otro caso
2.3.1. Ecuaciones lineales homogéneas.
La ecuación de recurrencia es de la forma:
a0t(n) + a1t(n-1) + ... + akt(n-k) = 0; ai constante
Caso sencillo: t(n) = x·t(n-1); t(0)= 1.
Solución: t(n) = x·t(n-1) = x·x·t(n-2) = x3 t(n-3) = ... = xn·t(0) ? t(n) = xn