SICP excercises 1.19 - Logarithmic time Fibonacci number generation

2015-04-25

This exercise describes a transformation $T_{pq}$, that, when applied to a pair $\left( a, b \right)$, transforms it according to $a \gets aq + bq + ap$ and $b \gets bp + aq$. The transformation used to generate Fibonacci numbers, starting from the pair $\left( 0, 1 \right)$, can be written as $a \gets a + b$ and $b \gets a$.

Note that the Fibonacci transformation is $T_{01}$ ($p=0$ and $q=1$).

The exercise asks us to show that applying any transformation $T_{pq}$ twice (or $T^2_{pq}$) to a pair $\left( a, b \right)$ is equivalent to applying the transformation $T_{p'q'}$ for some $p'$ and $q'$, and to find $p'$ and $q'$ in terms of $p$ and $q$.

Let’s apply the transformation once to get

$ a’ = aq + bq + ap $</div> <div>$ b’ = bp + aq $

Now apply the transformation once more.

$ a’’ = a’q + b’q + a’p $</div> <div>$ b’’ = b’p + a’q $

Substitute for $a'$ and $b'$ and rearrange

$ a’’ = ( aq + bq + ap ) q + ( bp + aq ) q + ( aq + bq + ap ) p $</div> <div>$ = ap^2 + bq^2 + 2aq^2 + 2apq + 2bpq $</div> <div>$ = a ( 2q^2 + p^2 + 2pq ) + b ( q^2 + 2pq ) $</div> <div>$ = a ( q^2 + 2pq ) + a ( p^2 + q^2 ) + b ( q^2 + 2pq ) $</div> <div>$ = a ( q^2 + 2pq ) + b ( q^2 + 2pq ) + a ( p^2 + q^2 ) $

$ b’’ = b’p + a’q $</div> <div>$ = ( bp + aq )p + ( aq + bq + ap )q $</div> <div>$ = bp^2 + apq + aq^2 + bq^2 + apq $</div> <div>$ = b( p^2 + q^2 ) + a( q^2 + 2pq ) $

Now comparing the final expressions for $a''$ and $b''$ with the original transformations, we note that transforming $\left( a,b \right)$ by $T^2_{pq}$ is equivalent to the single transformation $T_{p'q'}$, where $p' = p^2 + q^2$ and $q' = q^2 + 2pq$.