¿Cómo se consigue esta generalización de la secuencia de Fibonacci?

Question

Trabajando a través de SICP ahora mismo, y el ejercicio 1.19 describe las reglas de la secuencia de Fibonacci como una transformación $T$ por lo que $a + b \rightarrow a$ y $a \rightarrow b$ y señala que la aplicación de $T$ a los valores iniciales de 1 y 0 $n$ veces produce $Fib(n+1)$ y $Fib(n)$ . En este punto, introduce una clase más amplia de transformación $T_{pq}$ diciendo que $T$ es un caso especial en el que $p = 0$ y $q = 1$ y que la transformación $T_{pq}$ funciona de la siguiente manera:

$bq + aq + ap \rightarrow a$ y $bp + aq \rightarrow b$ .

A continuación, se nos pide que utilicemos esta fórmula para demostrar que es posible expresar de forma concisa las aplicaciones dobles del procedimiento para hacer que un algoritmo para calcular los números de fibonacci se ejecute en O(log n). Si quieres ver el texto completo del problema, está en la página 51 del libro enlazado arriba.

Ahora, puedo ver cómo funciona esto, pero no por qué. Mi pregunta es ¿en qué se basa esta generalización? ¿Qué característica de la secuencia de Fibonacci lo hizo evidente, o tiene alguna aplicación en un área diferente y la superposición se observó después?

Answer 1

No comprendo esa transformación $T_{pq}$ completamente, pero esto es lo que me viene a la mente cada vez que leo "Fibonacci" y " $O(\log n)$ "en una misma frase. Considere esta matriz: $$A=\begin{pmatrix}1&1\\1&0\end{pmatrix}.$$ This matrix is special because $$A \begin{pmatrix}F_{n}\\F_{n-1}\end{pmatrix} =\begin{pmatrix}1&1\\1&0\end{pmatrix} \begin{pmatrix}F_{n}\\F_{n-1}\end{pmatrix} =\begin{pmatrix}F_{n}+F_{n-1}\\F_{n}\end{pmatrix} =\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix},$$ and it also happens that $$A^n=\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}.$$ Calcule ambos $(A^n)^2$ y $A^{(2n)}$ (son iguales) y compararlos a la entrada: $$\begin{align}(A^n)^2&= \begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix} \cdot\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix} \\ &=\begin{pmatrix}F^2_{n+1}+F^2_n &F_{n+1}F_{n}+F_{n}F_{n-1}\\ F_{n}F_{n+1}+F_{n-1}F_n &F^2_n+F^2_{n-1}\end{pmatrix} \\ &\equiv \begin{pmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{pmatrix}=A^{(2n)}.\end{align}$$ Note that $$\begin{align}F_{2n}&=F_{n+1}F_n+F_{n-1}F_n=(F_{n+1}+F_{n-1})F_n=(F_{n+1}+F_{n-1})(F_{n+1}-F_{n-1})\\&=F^2_{n+1}-F^2_{n-1}.\end{align}$$ Así que está muy implícito que $F_{2n}$ puede calcularse en $O(\log_2 n)$ .