[[1,1],[1,0]]ⁿ nos da los números de Fibonacci.
La exponenciación de matrices es una técnica súper poderosa que sirve para calcular el término $n$-ésimo de una relación de recurrencia lineal de forma eficiente. Mientras que un enfoque iterativo estándar calcula los términos uno por uno (tardando un tiempo $O(n)$), la exponenciación de matrices te permite calcular el término $n$-ésimo en un tiempo $O(\log n)$ usando el método de exponenciación binaria (también conocido como exponenciación rápida). Esta velocidad es clave en matemáticas computacionales y en concursos avanzados como el AIME o USACO cuando $n$ es extremadamente grande (por ejemplo, $n = 10^{18}$).
La idea central es representar la transición entre términos consecutivos de una sucesión como una transformación lineal. Para la sucesión de Fibonacci, donde $F_{n+1} = F_n + F_{n-1}$, el estado del sistema en el paso $n$ depende de los dos valores anteriores. Si defines un vector de estado que contenga estos valores, puedes construir una matriz de transición constante $M$ tal que, al multiplicar el vector de estado actual por $M$, obtengas el siguiente vector de estado.
Aplicar esta transición repetidamente es equivalente a elevar la matriz $M$ a la potencia $n$. Esta técnica conecta el álgebra lineal con la combinatoria, dándote no solo un método de cálculo, sino también un marco para deducir propiedades como la Identidad de Cassini mediante determinantes y la Fórmula de Binet mediante eigenvalores y diagonalización.
La Matriz Q de Fibonacci Para la sucesión de Fibonacci definida por $F_0=0, F_1=1, F_{n} = F_{n-1} + F_{n-2}$, la identidad fundamental es: $$ \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix} $$
Recurrencia Lineal General Para una sucesión $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, la ecuación de transición es: $$ \begin{pmatrix} a_{n+1} \ a_n \end{pmatrix} = \begin{pmatrix} c_1 & c_2 \ 1 & 0 \end{pmatrix} \begin{pmatrix} a_n \ a_{n-1} \end{pmatrix} $$ Esto implica que: $$ \begin{pmatrix} a_{n+1} \ a_n \end{pmatrix} = \begin{pmatrix} c_1 & c_2 \ 1 & 0 \end{pmatrix}^n \begin{pmatrix} a_1 \ a_0 \end{pmatrix} $$
Identidad de Cassini (vía Determinantes) Si tomas el determinante de la identidad de la matriz de Fibonacci: $$ \det\left( \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n \right) = \det\begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix} $$ $$ (-1)^n = F_{n+1}F_{n-1} - F_n^2 $$
Teorema: Para la sucesión de Fibonacci definida por $F_0=0, F_1=1$ y $F_{n+1}=F_n+F_{n-1}$, lo siguiente se cumple para todos los enteros $n \geq 1$: $$ \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix} $$
Demostración por Inducción Matemática:
Toma $M = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$. Lo que hay que mostrar es que $M^n = \begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix}$.
Paso 1: Caso Base ($n=1$) Evalúa el lado izquierdo (LHS) y el lado derecho (RHS) para $n=1$: $$ \text{LHS} = M^1 = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} $$ $$ \text{RHS} = \begin{pmatrix} F_{1+1} & F_1 \ F_1 & F_{1-1} \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \ F_1 & F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} $$ Como LHS = RHS, el caso base se cumple.
Paso 2: Hipótesis de Inducción Supón que la fórmula funciona para algún entero positivo $k$. Es decir: $$ M^k = \begin{pmatrix} F_{k+1} & F_k \ F_k & F_{k-1} \end{pmatrix} $$
Paso 3: Paso Inductivo Ahora hay que mostrar que la fórmula se cumple para $n = k+1$. $$ M^{k+1} = M^k \cdot M $$ Sustituye la hipótesis de inducción para $M^k$ y la definición de $M$: $$ M^{k+1} = \begin{pmatrix} F_{k+1} & F_k \ F_k & F_{k-1} \end{pmatrix} \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} $$ Haz la multiplicación de matrices: $$ M^{k+1} = \begin{pmatrix} F_{k+1}(1) + F_k(1) & F_{k+1}(1) + F_k(0) \ F_k(1) + F_{k-1}(1) & F_k(1) + F_{k-1}(0) \end{pmatrix} $$ Simplifica los términos: $$ M^{k+1} = \begin{pmatrix} F_{k+1} + F_k & F_{k+1} \ F_k + F_{k-1} & F_k \end{pmatrix} $$ Aplica la relación de recurrencia de Fibonacci $F_{m} + F_{m-1} = F_{m+1}$:
Al sustituir esto de nuevo en la matriz, tienes: $$ M^{k+1} = \begin{pmatrix} F_{k+2} & F_{k+1} \ F_{k+1} & F_k \end{pmatrix} $$ Esto coincide con la forma del teorema para $n = k+1$.
Conclusión Por el Principio de Inducción Matemática, la fórmula es válida para todos los enteros $n \geq 1$. $\square$