Ecuaciones de recurrencia lineales
Necesito resolver el siguiente ejercicio mediante ecuaciones de recurrencia, hallando el polinomio característico y la explicación paso a paso:
La siguiente función modela, bajo condiciones iniciales nulas, el tiempo de un algoritmo. Calcular su forma explícita y orden exacto.
t(n) = 2 t(n-1) + 1
Gracias de antemano!
1 respuesta
Primero vamos a ponerla en la forma usual, con el subíndice n y siguientes, para ello sumamos uno al subíndice
t(n+1) = 2t(n) + 1
También suelen expresarse con todo a la izquierda
t(n+1) - 2t(n) - 1 = 0
Primero se resuelve la ecuación homogénea que es la misma quitando el 1
t(n+1) - 2t(n) = 0
el polinomio característico es
x-2 = 0
x = 2
luego la solución general de la homogénea es
A2^n para cualquier A € R
Lo segundo se halla una solución particular de la homogénea. Hay una regla que dice que si lo que le sobra a la homogénea es un polinomio se prueba con un polinomio del mismo grado. Como lo que le sobra es un 1 probamos con una constante como solución particular
t(n) = B
cono lo que
t(n+1) - 2t(n) - 1 = 0
será
B - 2B - 1 = 0
-B = 1
B =-1
Luego la solución particular es t(n)=-1
Y la solución general de la ecuación completa es la completa de la homogénea mas la particular de la completa
t(n) = A·2^n - 1
Ahora hagamos que tenga condiciones iniciales nulas, eso es que
t(0) = 0
A·2^0 - 1 = 0
A - 1 = 0
A = 0
Con lo cual la respuesta final es
t(n) = 2^n - 1
Y eso es todo.
Gracias por responder tan pronto, pero no tengo claro como resolver "t(n+1) - 2t(n) = 0" para obtener "x-2 = 0"... es que es la primera vez que me encuentro con ecuaciones de recurrencia y ando algo perdido...
El polinomio característico se obtiene de la ecuación de recurrencia cuyo subíndice menor sea n. Bueno, tampoco sería obligatorio pero siempre se ha hecho así. Entonces el coeficiente de t(n) se usa para x^0, el de t(n+1) para x^1, el de t(n+2) para x^2, etc.
Tu ecuación era
t(n) = 2 t(n-1) + 1
t(n) - 2t(n-1) - 1 = 0
Haciendo los cambios para que el término menor sea n, es:
t(n+1) - 2t(n) - 1 = 0
y el polinomio característico tiene 2 para x^0 y 1 para x^1, es
x-2
y hay que hallar las raíces del polinomio característico
x-2= 0
x = 2
Si la ecuación fuese por ejemplo
t(n+3) - 5t(n+2) + 6t(n+1) + n^2 -2 = 0
La ponemos con t(n) como término menor
t(n+2) - 5t(n+1) + 6t(n) + n^2 - 2 = 0
Y el polinomio característico es
x^2 - 5x + 6 = 0
Las soluciones son 2 y 3 como puedes comprobar
Y la solución general de la homogénea sería
A·2^n + B·3^n con A,B € R
Es todo teoría. Aunque el método que he usado es el general y puede que te hayan enseñado un método más sencillo para esa ecuación fácil.
