Fibonacci - andres726127/An-lisis-de-Algoritmos GitHub Wiki

package fibbonaccib1;

import java.util.Scanner;

public class FibbonacciB1 {

    public static int fibonacciRecursivo(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacciRecursivo(n - 1) + fibonacciRecursivo(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 0;
        System.out.print("Ingrese un número para encontrar el fibonacci: ");
        while (!sc.hasNextInt()) {            
            System.err.println("Error: Se necesita un número entero!");
            System.out.print("Intente de nuevo: ");
            sc.next();
        }
        n = sc.nextInt();
        for (int i = 0; i <= n; i++) {
            System.out.print(fibonacciRecursivo(i) + " ");
        }
    }
}

2. Identificación de la Recurrencia

La función de Fibonacci se define mediante la siguiente relación de recurrencia:

$$ F(n) = \begin{cases} 0 & \text{si } n = 0 \ 1 & \text{si } n = 1 \ F(n-1) + F(n-2) & \text{si } n \geq 2 \end{cases} $$

Esta es una relación recursiva no lineal de segundo orden con condiciones iniciales. Se utiliza ampliamente en problemas de conteo y en el análisis de algoritmos recursivos.

---

3. Ecuación General (Fórmula Cerrada)

Para resolver la recurrencia, se utiliza la técnica de ecuaciones características.

La ecuación característica es:

$$ x^2 = x + 1 \Rightarrow x^2 - x - 1 = 0 $$

Las soluciones son:

$$ \phi = \frac{1 + \sqrt{5}}{2}, \quad \psi = \frac{1 - \sqrt{5}}{2} $$

La solución general de la sucesión es la fórmula de Binet:

$$ F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}} $$

Esta expresión permite calcular directamente el término enésimo de la sucesión sin necesidad de recurrencia.

---

4. Demostración por Inducción

Paso base:

Para ( n = 0 ):

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

Para ( n = 1 ):

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

Coincide con la definición original de la sucesión.

Paso inductivo:

Supongamos que:

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

Queremos demostrar que:

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

Usando la propiedad de las potencias:

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

Sustituyendo en la fórmula:

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

Por lo tanto, la fórmula queda demostrada por inducción matemática.