Sucesión de Fibonacci

Teoría

La sucesión de Fibonacci es una serie de números donde cada número es la suma de los dos anteriores, y normalmente empieza con 0 y 1. Aunque a veces se presenta como una simple curiosidad aritmética, en el mundo de la combinatoria, la sucesión de Fibonacci es una herramienta fundamental para resolver problemas de conteo que tienen estructuras recursivas. Aparece de forma natural en situaciones donde puedes dividir un problema de tamaño $n$ en casos que no se traslapan basándote en el último paso: por lo general, un "paso pequeño" que reduce el problema a tamaño $n-1$ o un "paso grande" que lo reduce a tamaño $n-2$.

Esta sucesión está en todos lados en las matemáticas de competencia, sobre todo en problemas de mosaicos (tilings), conteo de caminos y cadenas binarias. Por ejemplo, el número de formas de cubrir un tablero de $1 \times n$ usando cuadrados de $1 \times 1$ y dominós de $1 \times 2$ te lo dan los números de Fibonacci. De la misma forma, la cantidad de cadenas binarias de longitud $n$ que no tienen unos consecutivos es un número de Fibonacci. Si reconoces la relación recursiva $a_n = a_{n-1} + a_{n-2}$, puedes identificar de inmediato que la estructura es de Fibonacci, lo que cambia el problema de estar contando a mano a simplemente calcular un término específico $F_n$.

Más allá del conteo básico, la sucesión de Fibonacci tiene propiedades algebraicas profundas y relaciones con la teoría de números. Conecta las matemáticas discretas con el mundo continuo a través de la Razón Áurea ($\phi$), que aparece en la fórmula cerrada para el $n$-ésimo término (la Fórmula de Binet). En competencias avanzadas como el AIME, a menudo vas a tener que manipular identidades de Fibonacci, analizar propiedades de divisibilidad (como $\gcd(F_m, F_n) = F_{\gcd(m,n)}$) o usar el comportamiento de la sucesión módulo $k$ (periodos de Pisano).

Fórmulas Clave

Definición y Recurrencia La sucesión se define así: $$F_n = F_{n-1} + F_{n-2} \quad \text{para } n \ge 2$$ Condiciones iniciales estándar: $F_0 = 0, F_1 = 1$. La sucesión empieza: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$

Fórmula de Binet (Forma Cerrada) $$F_n = \frac{\phi^n - \psi^n}{\phi - \psi} = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$$ donde $\phi = \frac{1 + \sqrt{5}}{2}$ (la Razón Áurea) y $\psi = \frac{1 - \sqrt{5}}{2} = -1/\phi$.

Identidad de Cassini $$F_{n-1}F_{n+1} - F_n^2 = (-1)^n$$

Identidades de Suma Suma de los primeros $n$ términos: $$\sum_{i=1}^n F_i = F_{n+2} - 1$$ Suma de cuadrados: $$\sum_{i=1}^n F_i^2 = F_n F_{n+1}$$

Interpretación Combinatoria (Mosaicos) El número de formas de cubrir un tablero de $1 \times n$ con cuadrados ($1 \times 1$) y dominós ($1 \times 2$) es $F_{n+1}$.

Propiedad de Teoría de Números $$\gcd(F_m, F_n) = F_{\gcd(m,n)}$$

Demostración

Teorema: Demostración de la Fórmula de Binet La idea es obtener la expresión cerrada para la recurrencia $F_n = F_{n-1} + F_{n-2}$ con las condiciones iniciales $F_0 = 0$ y $F_1 = 1$.

Paso 1: La Ecuación Característica Supón que existe una solución de forma geométrica $F_n = r^n$ para alguna constante $r \neq 0$. Si sustituyes esto en la relación de recurrencia, obtienes: $$r^n = r^{n-1} + r^{n-2}$$ Al dividir ambos lados entre $r^{n-2}$ (ya que $r \neq 0$), llegas a la ecuación cuadrática característica: $$r^2 - r - 1 = 0$$

Paso 2: Resolver para las Raíces Usando la fórmula general para cuadráticas, las raíces de $r^2 - r - 1 = 0$ son: $$\phi = \frac{1 + \sqrt{5}}{2} \quad \text{y} \quad \psi = \frac{1 - \sqrt{5}}{2}$$ Como hay dos raíces distintas, la solución general de la recurrencia lineal homogénea es una combinación lineal de las potencias de estas raíces: $$F_n = c_1 \phi^n + c_2 \psi^n$$ donde $c_1$ y $c_2$ son constantes que se determinan con las condiciones iniciales.

Paso 3: Aplicar las Condiciones Iniciales Usa $F_0 = 0$ y $F_1 = 1$ para encontrar $c_1$ y $c_2$.

Para $n=0$: $$F_0 = c_1 \phi^0 + c_2 \psi^0 \implies c_1 + c_2 = 0 \implies c_2 = -c_1$$

Para $n=1$: $$F_1 = c_1 \phi^1 + c_2 \psi^1 = 1$$ Sustituyendo $c_2 = -c_1$: $$c_1 \phi - c_1 \psi = 1$$ $$c_1 (\phi - \psi) = 1$$

Calcula la diferencia $\phi - \psi$: $$\phi - \psi = \frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2} = \frac{2\sqrt{5}}{2} = \sqrt{5}$$

Entonces: $$c_1(\sqrt{5}) = 1 \implies c_1 = \frac{1}{\sqrt{5}}$$ Y como $c_2 = -c_1$: $$c_2 = -\frac{1}{\sqrt{5}}$$

Paso 4: Sustitución Final Sustituye $c_1$ y $c_2$ de vuelta en la forma general: $$F_n = \frac{1}{\sqrt{5}} \phi^n - \frac{1}{\sqrt{5}} \psi^n$$ $$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

Con esto termina la deducción de la Fórmula de Binet. $\square$