35. Resolución básica de recurrencias

Resolver una recurrencia significa encontrar una fórmula cerrada que calcule aₙ directamente a partir de n, sin generar todos los términos intermedios. Es una herramienta clave para analizar algoritmos y sucesiones discretas.

35.1 Introducción

En el tema anterior aprendimos a **definir** relaciones de recurrencia y a generar términos paso a paso. Ese método es correcto pero ineficiente si necesitamos, por ejemplo, el término número 10 000.

La **resolución de recurrencias** busca una expresión explícita aₙ = f(n) que produzca el mismo valor que la definición recursiva. Esta fórmula cerrada permite evaluar cualquier término en tiempo constante (o casi constante) y comprender el crecimiento de la sucesión.

35.2 Fórmula Cerrada

Una **fórmula cerrada** (o solución explícita) de una sucesión es una expresión que calcula aₙ usando solo n y constantes, sin referirse a otros términos de la sucesión:

Definición recursiva: aₙ = 2·aₙ₋₁, a₁ = 3 Fórmula cerrada: aₙ = 3 · 2ⁿ⁻¹

Verificar que una fórmula cerrada es correcta consiste en comprobar que produce los mismos valores que la recurrencia para todos los n del dominio.

35.3 Sustitución Iterativa (Unfolding)

La técnica más accesible para resolver recurrencias simples es la **sustitución iterativa**: expandir la recurrencia reemplazando repetidamente cada término por su definición hasta detectar un patrón.

Ejemplo: Resolver aₙ = 2·aₙ₋₁ + 1 con a₁ = 1.

aₙ = 2·aₙ₋₁ + 1 = 2·(2·aₙ₋₂ + 1) + 1 = 2²·aₙ₋₂ + 2 + 1 = 2³·aₙ₋₃ + 2² + 2 + 1 = … = 2ⁿ⁻¹·a₁ + (2ⁿ⁻² + 2ⁿ⁻³ + … + 2 + 1) = 2ⁿ⁻¹·1 + (2ⁿ⁻¹ − 1) = 2ⁿ − 1

Tras k sustituciones se reconoce una progresión geométrica en la suma, lo que permite cerrar la expresión.

35.4 Recurrencias Lineales de Orden 1

Homogénea: aₙ = r · aₙ₋₁ con a₁ dado.

Solución: aₙ = a₁ · rⁿ⁻¹ (Es una progresión geométrica.)

No homogénea: aₙ = r · aₙ₋₁ + s con r ≠ 1.

Solución: aₙ = (a₁ − s/(1−r)) · rⁿ⁻¹ + s/(1−r) Caso del ejemplo anterior: r=2, s=1, a₁=1 → aₙ = (1 − 1) · 2ⁿ⁻¹ + 1 = 2ⁿ − 1

Orden 2 (introducción): Para recurrencias como Fibonacci aₙ = aₙ₋₁ + aₙ₋₂, se buscan soluciones de la forma aₙ = c · λⁿ, lo que conduce a la **ecuación característica** λ² = λ + 1. Su estudio completo excede el nivel básico, pero el principio es el mismo: convertir la recurrencia en una ecuación algebraica.

35.5 Simulador: Recurrencia vs Fórmula Cerrada

El simulador compara, para cada n, el valor obtenido **generando términos con la recurrencia** frente al calculado con la **fórmula cerrada**. Si la resolución es correcta, ambas columnas coinciden (marca ✓). Avanza fila a fila para verificar la equivalencia.

Verificador de Soluciones Cerradas Fila 0 / 7
Recurrencia: aₙ = 2·aₙ₋₁, a₁=3. Fórmula cerrada: aₙ = 3·2ⁿ⁻¹.

35.6 Resolución en Programación

En la práctica, conviene implementar ambos métodos: la recurrencia iterativa para generar términos y la fórmula cerrada para evaluar posiciones lejanas con eficiencia. Comparar ambos resultados sirve como prueba de la solución.

// Calcular a_n por recurrencia iterativa
function porRecurrencia(n, a1, paso) {
  let actual = a1;
  for (let i = 2; i <= n; i++) {
    actual = paso(actual);
  }
  return actual;
}

// Fórmulas cerradas resueltas
const cerradaGeometrica = (n) => 3 * Math.pow(2, n - 1);
const cerradaAritmetica = (n) => 5 + (n - 1) * 2;
const cerradaNoHomogenea = (n) => Math.pow(2, n) - 1;

function verificar(n, recurrencia, cerrada, etiqueta) {
  const vRec = porRecurrencia(n, recurrencia.a1, recurrencia.paso);
  const vCer = cerrada(n);
  const ok = vRec === vCer;
  console.log(`${etiqueta} n=${n}: rec=${vRec}, cerrada=${vCer} → ${ok ? 'OK' : 'ERROR'}`);
  return ok;
}

verificar(10,
  { a1: 1, paso: (x) => 2 * x + 1 },
  cerradaNoHomogenea,
  "No homogénea"
);
// No homogénea n=10: rec=1023, cerrada=1023 → OK

console.log("a_20 geométrica (cerrada):", cerradaGeometrica(20));
// a_20 geométrica (cerrada): 1572864

35.7 Errores Comunes

  • Confundir fórmula cerrada con implementación iterativa: Un bucle que genera términos no es una solución cerrada; la fórmula debe depender solo de n.
  • Olvidar verificar con condiciones iniciales: Una expresión puede satisfacer la recurrencia pero fallar en a₁ si se omitió la constante de integración discreta.
  • Aplicar la fórmula de orden 1 no homogénea con r = 1: Si r = 1, la fórmula con denominador (1 − r) no es válida; el caso se resuelve por suma aritmética.
  • Errores de índice al sustituir: Al hacer unfolding, mantener coherente si la sucesión empieza en n = 1 o en n = 0.

35.8 Qué debes recordar de este tema

  • Resolver una recurrencia significa hallar una fórmula cerrada aₙ = f(n).
  • La **sustitución iterativa** expande la recurrencia hasta revelar un patrón.
  • aₙ = r·aₙ₋₁ tiene solución aₙ = a₁·rⁿ⁻¹.
  • aₙ = r·aₙ₋₁ + s (con r ≠ 1) combina parte homogénea y particular.
  • Siempre verifica comparando la fórmula cerrada con la generación iterativa.

35.9 Conclusión

Las técnicas básicas de resolución permiten transformar definiciones recursivas en fórmulas explícitas, facilitando el análisis de complejidad y el cálculo de términos lejanos. Con esto cerramos el bloque de sucesiones y recurrencias del curso.

A partir del próximo tema cambiamos de dominio: estudiaremos la **introducción a funciones booleanas**, funciones cuyas entradas y salidas son valores de verdad, fundamentales para la lógica digital y la programación condicional.

Volver al índice