La regla F(n) = F(n-1) + F(n-2).
La recurrencia de Fibonacci es una de las relaciones más fundamentales en combinatoria y teoría de números. Define una sucesión de números donde cada término es la suma de los dos anteriores. Aunque la definimos formalmente con condiciones iniciales (normalmente $F_0=0$ y $F_1=1$) y la relación de recurrencia, su verdadero poder en las matemáticas de competencia está en sus interpretaciones combinatorias. La recurrencia modela un montón de fenómenos naturales y matemáticos, especialmente los que tienen que ver con crecimiento o arreglos donde el estado actual depende totalmente de la historia inmediata.
En el contexto de las competencias AMC y AIME, vas a usar la recurrencia de Fibonacci seguido para resolver problemas de conteo con restricciones que prohíben elegir elementos adyacentes, o problemas de mosaicos y caminos. La intuición más común es el "Modelo de la Escalera" o el "Modelo de Mosaicos". Si estás subiendo una escalera y puedes dar pasos de tamaño 1 o 2, el número de formas de llegar al escalón $n$ es un número de Fibonacci. Esto pasa porque para llegar al escalón $n$, tienes que haber venido justo del escalón $n-1$ (dando un paso de 1) o del escalón $n-2$ (dando un paso de 2).
Entender esta recurrencia te permite reducir problemas de conteo complejos a relaciones de recurrencia lineales. En lugar de intentar contar