📘 Estudio de Recurrencias - Por Emilio Peña

Creado por Emilio Peña · Última edición reciente

---

🧭 Tabla de Contenidos

1. Introducción al problema de Fibonacci
2. Código en Java: Soluciones Recursiva e Iterativa
3. Análisis de la Recurrencia
4. Derivación de la Fórmula General
5. Prueba por Inducción Matemática

---

🧩 Introducción al problema de Fibonacci

La secuencia de Fibonacci es una serie matemática donde cada número es la suma de los dos anteriores. Es ampliamente usada en computación, matemáticas y ciencias naturales.

---

💻 Código en Java: Soluciones Recursiva e Iterativa

Aquí presentamos dos implementaciones del algoritmo de Fibonacci: una recursiva simple y otra iterativa eficiente.

public class Fibonacci {

    // Solución recursiva simple
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    // Solución iterativa eficiente
    public static int fibonacciIterativo(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci recursivo de " + n + ": " + fibonacci(n));
        System.out.println("Fibonacci iterativo de " + n + ": " + fibonacciIterativo(n));
    }
}

---

🔍 Análisis de la Recurrencia

La recurrencia que define la sucesión de Fibonacci es:

[ F(n) = F(n - 1) + F(n - 2) ]

Con condiciones iniciales:

[ F(0) = 0, \quad F(1) = 1 ]

---

🧠 Derivación de la Fórmula General

Mediante resolución algebraica de la recurrencia, obtenemos la fórmula cerrada o fórmula de Binet:

[ F(n) = \frac{\varphi^n - \psi^n}{\sqrt{5}} ]

Donde:

• \\( \\varphi = \\frac{1 + \\sqrt{5}}{2} \\) (número áureo)
• \\( \\psi = \\frac{1 - \\sqrt{5}}{2} \\)

---

🧠 Prueba por Inducción Matemática

Demostramos que la fórmula cerrada es válida para todo $n \geq 0$.

---

🔹 Base de la inducción:

$$ F(0) = \frac{1 - 1}{\sqrt{5}} = 0 $$

$$ F(1) = \frac{\varphi - \psi}{\sqrt{5}} = 1 $$

---

🔹 Paso inductivo:

Asumimos que:

$$ F(k) = \frac{\varphi^k - \psi^k}{\sqrt{5}}, \quad F(k-1) = \frac{\varphi^{k-1} - \psi^{k-1}}{\sqrt{5}} $$

Entonces:

$$ F(k+1) = F(k) + F(k-1) $$

Reemplazando las expresiones:

$$ F(k+1) = \frac{\varphi^k - \psi^k}{\sqrt{5}} + \frac{\varphi^{k-1} - \psi^{k-1}}{\sqrt{5}} $$

Agrupamos:

$$ F(k+1) = \frac{\varphi^k + \varphi^{k-1} - (\psi^k + \psi^{k-1})}{\sqrt{5}} $$

Sabemos que:

$$ \varphi^{k+1} = \varphi^k + \varphi^{k-1}, \quad \psi^{k+1} = \psi^k + \psi^{k-1} $$

Entonces:

$$ F(k+1) = \frac{\varphi^{k+1} - \psi^{k+1}}{\sqrt{5}} $$

---

✅ Por lo tanto, la fórmula se cumple para todo $n \geq 0$ por el principio de inducción matemática.