AALIE

Método de la Ecuación Característica

Aplicabilidad, procedimiento algebraico, casos de raíces, ejemplos resueltos y errores comunes.

Cuándo aplica la Ecuación Característica

El método de la ecuación característica es un método algebraico para resolver ciertas recurrencias donde el tamaño baja por resta fija, no por división. Su caso más limpio es una ecuación de recurrencia lineal homogénea con coeficientes constantes.

Forma general de una ERLH

T (n) = c_{1} T (n - 1) + c_{2} T (n - 2) + \dots + c_{k} T (n - k)

En esta expresión, cada $c_{i}$ representa un coeficiente constante que multiplica a los términos anteriores de la recurrencia. El valor de $k$ indica el orden de la ecuación, es decir, cuántos pasos hacia atrás necesitamos conocer para calcular el valor actual.

Aplicabilidad del método

Situación	¿Aplica?	Razón
$T (n) = T (n - 1) + T (n - 2)$	Sí	Es lineal, homogénea y con coeficientes constantes.
$T (n) = 2 T (n - 1) + 1$	Sí, pero no directamente como homogénea	Es no homogénea por el término $+ 1$ ; requiere solución particular.
$T (n) = T (n - 1) + n$	Sí, con extensión	Es lineal con coeficientes constantes, pero no homogénea.
$T (n) = 2 T (n /2) + n$	No directamente	Es divide y vencerás. Requiere Teorema Maestro, árbol, sustitución o cambio de variable previo.
$T (n) = n T (n - 1) + 1$	No	El coeficiente de $T (n - 1)$ depende de $n$ .
$T (n) = T (n - 1)^{2} + 1$	No	No es lineal porque $T$ aparece elevado al cuadrado.

No mezclar métodos

La ecuación característica no es el método natural para $T (n) = a T (n / b) + f (n)$ . Esa forma pertenece a Divide y Vencerás. Forzar ecuación característica ahí, sin cambio de variable, es una mala señal de análisis.

Concepto fundamental: qué es una ERLH

Ecuación de Recurrencia Lineal Homogénea

Una ERLH es una recurrencia lineal, homogénea y con coeficientes constantes. Esa triple condición es obligatoria para aplicar directamente el polinomio característico sin solución particular.

Condiciones de una ERLH

Propiedad	Significado	Válido	Inválido
Lineal	Los términos $T$ aparecen a la potencia 1 y no se multiplican entre sí.	$T (n) = T (n - 1) + T (n - 2)$	$T (n) = T (n - 1)^{2}$
Homogénea	No hay términos externos independientes de $T$ .	$T (n) = 2 T (n - 1)$	$T (n) = 2 T (n - 1) + 1$
Coeficientes constantes	Los coeficientes de cada $T (n - k)$ no dependen de $n$ .	$T (n) = 3 T (n - 1) - 2 T (n - 2)$	$T (n) = n T (n - 1)$

Forma estándar

T (n) - c_{1} T (n - 1) - c_{2} T (n - 2) - \dots - c_{k} T (n - k) = 0

La forma estándar iguala la recurrencia a cero para facilitar la construcción del polinomio característico. Al sustituir $T (n)$ por una solución del tipo $r^{n}$ , buscamos las raíces $r_{i}$ que satisfacen esta igualdad algebraica.

Homogénea no significa sencilla

Una recurrencia puede ser lineal y aun así no ser homogénea. Si aparece $+ 1$ , $+ n$ o $+ 2^{n}$ fuera de los términos $T (\cdot)$ , ya no es homogénea.

Paso a paso — Ecuación Característica

Detectar la recurrencia y verificar que es ERLH. Confirma linealidad, homogeneidad y coeficientes constantes. Si hay término externo $g (n) \neq = 0$ , separa parte homogénea y solución particular.
Escribir la ecuación en forma estándar. Mueve todo al lado izquierdo para obtener una igualdad contra cero.
Plantear el cambio $T (n) = r^{n}$ . Sustituye $T (n), T (n - 1), \dots, T (n - k)$ por potencias de $r$ .
Dividir por la menor potencia común. Normalmente se divide por $r^{n - k}$ para obtener un polinomio de grado $k$ .
Calcular las raíces. Las raíces pueden ser distintas, repetidas o complejas.
Construir la solución general. La forma depende de la multiplicidad de las raíces.
Aplicar condiciones iniciales. Sustituye $T (0), T (1), \dots$ para resolver las constantes.
Identificar la raíz dominante. La raíz de mayor valor absoluto determina el crecimiento principal.

Derivación del polinomio característico

Forma estándar

Primero se pasa la recurrencia al lado izquierdo para compararla contra cero.

T (n) - c_{1} T (n - 1) - c_{2} T (n - 2) - \dots - c_{k} T (n - k) = 0

Sustitución

Se usa $T (n) = r^{n}$ como hipótesis algebraica.

r^{n} - c_{1} r^{n - 1} - c_{2} r^{n - 2} - \dots - c_{k} r^{n - k} = 0

Dividir por la menor potencia

Se divide por $r^{n - k}$ para eliminar el factor común.

\frac{r ^{n} - c _{1} r ^{n - 1} - \dots - c _{k} r ^{n - k}}{r ^{n - k}} = 0

Polinomio característico

Este es el polinomio que se resuelve para encontrar las raíces características.

r^{k} - c_{1} r^{k - 1} - c_{2} r^{k - 2} - \dots - c_{k} = 0

Forms de solución según las raíces

Solución general según las raíces

Caso	Raíces	Solución general	Comentario
Raíces distintas	$r_{1}, r_{2}, \dots, r_{k}$	$T (n) = C_{1} r_{1}^{n} + C_{2} r_{2}^{n} + \dots + C_{k} r_{k}^{n}$	Cada raíz aporta un término exponencial.
Raíz repetida	$r$ con multiplicidad $m$	$(C_{0} + C_{1} n + C_{2} n^{2} + \dots + C_{m - 1} n^{m - 1}) r^{n}$	La multiplicidad introduce factores polinomiales en $n$ .
Raíces complejas conjugadas	$r = ρ (cos θ \pm i sin θ)$	$ρ^{n} (A cos n θ + B sin n θ)$	Aparece en análisis algebraico general; no suele ser el caso principal en los ejemplos básicos del curso.

Raíz dominante

Si la solución tiene varias raíces, domina la de mayor valor absoluto. Por ejemplo, si aparecen $1.61 8^{n}$ y $(- 0.618)^{n}$ , el primer término domina.

Cuidado con cancelaciones

La raíz dominante determina el orden salvo que las condiciones iniciales cancelen exactamente su coeficiente. En ejercicios básicos esto casi nunca ocurre, pero matemáticamente puede pasar.

Ejemplo 1 — Fibonacci

Resolver la recurrencia de Fibonacci:

Recurrencia

T (n) = T (n - 1) + T (n - 2), T (0) = 0, T (1) = 1

Esta es la recurrencia clásica de Fibonacci, donde cada término es la suma de los dos anteriores. Resolverla mediante la ecuación característica nos permite encontrar una fórmula directa (cerrada) sin tener que calcular todos los valores intermedios.

Solución paso a paso

Pasar a forma estándar

Se mueven todos los términos al lado izquierdo.

T (n) - T (n - 1) - T (n - 2) = 0

Sustituir T(n)=r^n

Cada término $T (n - k)$ se reemplaza por $r^{n - k}$ .

r^{n} - r^{n - 1} - r^{n - 2} = 0

Dividir por r^(n−2)

El polinomio característico es cuadrático.

\frac{r ^{n} - r ^{n - 1} - r ^{n - 2}}{r ^{n - 2}} = 0 \Rightarrow r^{2} - r - 1 = 0

Resolver raíces

Las raíces son distintas: $φ = \frac{1 + 5}{2}$ y $ψ = \frac{1 - 5}{2}$ .

r = \frac{1 \pm 5}{2}

Construir solución general

Como las raíces son distintas, cada una aporta un término exponencial.

T (n) = C_{1} φ^{n} + C_{2} ψ^{n}

Aplicar T(0)=0

La primera condición inicial relaciona ambas constantes.

T (0) = C_{1} + C_{2} = 0 \Rightarrow C_{2} = - C_{1}

Aplicar T(1)=1

Al reemplazar $C_{2} = - C_{1}$ , queda una sola constante por resolver.

T (1) = C_{1} φ + C_{2} ψ = 1 \Rightarrow C_{1} (φ - ψ) = 1

Resolver constantes

La diferencia entre las raíces es $5$ .

φ - ψ = 5 \Rightarrow C_{1} = \frac{1}{5}, C_{2} = - \frac{1}{5}

Forma cerrada

Esta es la forma cerrada de Fibonacci conocida como fórmula de Binet.

T (n) = \frac{φ ^{n} - ψ ^{n}}{5}

Raíz dominante

El término con $ψ^{n}$ se vuelve despreciable frente a $φ^{n}$ .

∣ φ ∣ \approx 1.618 > ∣ ψ ∣ \approx 0.618

Resultado

$T (n) \in Θ (φ^{n})$ , donde $φ \approx 1.618$ . Además, $T (n) \in o (2^{n})$ porque $1.61 8^{n}$ crece estrictamente más lento que $2^{n}$ .

Ejemplo 2 — Raíz repetida

Resolver la recurrencia:

Recurrencia

T (n) = 2 T (n - 1) - T (n - 2), T (0) = 1, T (1) = 2

Cuando una raíz característica tiene multiplicidad $m > 1$ (se repite), la solución general debe incluir factores polinomiales en $n$ para mantener la independencia lineal de los términos.

Solución paso a paso

Forma estándar

La recurrencia es lineal homogénea con coeficientes constantes.

T (n) - 2 T (n - 1) + T (n - 2) = 0

Polinomio característico

Se obtiene sustituyendo $T (n) = r^{n}$ .

r^{2} - 2 r + 1 = 0

Factorizar

La raíz $r = 1$ tiene multiplicidad 2.

(r - 1)^{2} = 0

Solución general

La raíz repetida introduce el factor $n$ .

T (n) = (C_{0} + C_{1} n) 1^{n} = C_{0} + C_{1} n

Aplicar condiciones iniciales

Las dos condiciones iniciales determinan las dos constantes.

T (0) = C_{0} = 1, T (1) = 1 + C_{1} = 2 \Rightarrow C_{1} = 1

Resultado

El crecimiento final es lineal.

T (n) = 1 + n \in Θ (n)

Ejemplo 3 — Torres de Hanói como no homogénea

Torres de Hanói produce la recurrencia:

Recurrencia

T (n) = 2 T (n - 1) + 1, T (0) = 0

Esta recurrencia es no homogénea debido al término constante $+ 1$ (término forzante). Para resolverla, calculamos primero la solución homogénea y luego le sumamos una solución particular que capture el efecto de ese término externo.

No es homogénea

El término $+ 1$ impide aplicar solo la parte homogénea. Hay que sumar una solución particular.

Solución paso a paso

Parte homogénea

Se elimina temporalmente el término forzante.

T_{h} (n) = 2 T_{h} (n - 1)

Polinomio característico

La parte homogénea tiene una sola raíz.

r - 2 = 0 \Rightarrow r = 2

Solución homogénea

La raíz $2$ produce el término exponencial.

T_{h} (n) = C 2^{n}

Proponer solución particular constante

Como el término forzante es constante, se intenta una solución particular constante.

T_{p} (n) = A

Resolver A

Se sustituye $T_{p} (n) = A$ en la recurrencia original.

A = 2 A + 1 \Rightarrow A = - 1

Solución general

La solución total es la suma de la homogénea y la particular.

T (n) = C 2^{n} - 1

Aplicar T(0)=0

La condición inicial fija la constante.

0 = C 2^{0} - 1 \Rightarrow C = 1

Resultado

El crecimiento es exponencial.

T (n) = 2^{n} - 1 \in Θ (2^{n})

Ejemplo 4 — Tribonacci

Resolver asintóticamente la recurrencia:

Recurrencia

T (n) = T (n - 1) + T (n - 2) + T (n - 3)

Tribonacci es una extensión de Fibonacci que suma los tres términos anteriores, lo que produce un polinomio característico de tercer grado. La raíz real de mayor valor absoluto determinará el crecimiento exponencial dominante de la solución.

Solución asintótica

Forma estándar

Es una ERLH de orden 3.

T (n) - T (n - 1) - T (n - 2) - T (n - 3) = 0

Polinomio característico

Se obtiene con la sustitución $T (n) = r^{n}$ .

r^{3} - r^{2} - r - 1 = 0

Raíz dominante

El polinomio tiene una raíz real dominante conocida como constante tribonacci.

r_{1} \approx 1.839286

Resultado asintótico

Para complejidad basta identificar la raíz dominante; no siempre es necesario resolver todo el sistema de constantes.

T (n) \in Θ (1.83928 6^{n})

Árbol de decisión del método

Decisión de aplicabilidad

Renderizando diagrama...

Errores típicos

Errores frecuentes en ecuación característica

Error	Por qué está mal	Corrección
Aplicarla directamente a $T (n) = 2 T (n /2) + n$	Esa recurrencia no baja por resta fija; baja por división.	Usar Teorema Maestro, árbol de recursión o cambio de variable.
Olvidar pasar todo al lado izquierdo	El polinomio característico sale con signos incorrectos.	Escribir primero la forma estándar contra cero.
Usar solo la parte homogénea en una no homogénea	Ignora el término forzante y produce una solución incompleta.	Sumar solución homogénea y solución particular.
Tratar raíces repetidas como distintas	Se pierden factores polinomiales como $n$ o $n^{2}$ .	Usar $(C_{0} + C_{1} n + \dots + C_{m - 1} n^{m - 1}) r^{n}$ .
No aplicar condiciones iniciales	Queda una familia de soluciones, no la solución de la recurrencia dada.	Resolver las constantes con $T (0), T (1), \dots$ .
Confundir solución cerrada con orden	La solución cerrada puede tener varios términos; la complejidad depende del dominante.	Después de cerrar, identificar la raíz dominante y expresar $Θ$ .

Resumen operativo

Receta mínima

Verificar que la recurrencia sea lineal y tenga coeficientes constantes.
Si es homogénea, aplicar el método directo; si no, separar homogénea y particular.
Pasar a forma estándar igualada a cero.
Sustituir $T (n) = r^{n}$ .
Obtener y resolver el polinomio característico.
Construir la solución general según raíces distintas, repetidas o complejas.
Aplicar condiciones iniciales para hallar constantes.
Identificar la raíz dominante y concluir el orden asintótico.

Fórmulas clave

ERLH

Forma de entrada principal del método.

T (n) = c_{1} T (n - 1) + c_{2} T (n - 2) + \dots + c_{k} T (n - k)

Polinomio característico

Se obtiene al sustituir $T (n) = r^{n}$ .

r^{k} - c_{1} r^{k - 1} - c_{2} r^{k - 2} - \dots - c_{k} = 0

Raíces distintas

Cada raíz distinta aporta un término.

T (n) = C_{1} r_{1}^{n} + C_{2} r_{2}^{n} + \dots + C_{k} r_{k}^{n}

Raíz repetida

Una raíz de multiplicidad $m$ genera $m$ términos asociados.

(C_{0} + C_{1} n + \dots + C_{m - 1} n^{m - 1}) r^{n}

Dominancia

La raíz de mayor valor absoluto determina el crecimiento principal.

T (n) \in Θ (∣ r_{ma x} ∣^{n}) si r_{ma x} domina sin cancelaci \overset{o}{ˊ} n