2
$\begingroup$

Working through SICP right now, and exercise 1.19 describes the Fibonacci sequence rules as a transformation $T$ whereby $a + b \rightarrow a$ and $a \rightarrow b$, and points out that applying $T$ to the starting values of 1 and 0 $n$ times yields $Fib(n+1)$ and $Fib(n)$. At this point, it introduces a broader class of transformation $T_{pq}$, saying that $T$ is a special case where $p = 0$ and $q = 1$, and that the transformation $T_{pq}$ works as follows:

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

We are then asked to use this formula to demonstrate that it's possible to express double applications of the procedure concisely to make an algorithm for computing fibonacci numbers run in O(log n). If you'd like to look at the full text of the problem, it is on page 51 of the book linked above.

Now, I can see how this works, but not why. My question is on what basis was this generalization achieved? What feature of the Fibonacci sequence made this apparent, or does it have some application in a different are and the overlap was observed later?

$\endgroup$
2
$\begingroup$

I don't comprehend that transformation $T_{pq}$ quite fully, but this is what comes to mind whenever I read "Fibonacci" and "$O(\log n)$" in a same sentence. Consider this matrix: $$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}.$$ Compute both $(A^n)^2$ and $A^{(2n)}$ (they are equal) and compare them entrywise: $$\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}$$ So it is heavily implied that $F_{2n}$ can be computed in $O(\log_2 n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.