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 $
$ b' = bp + aq $

Now apply the transformation once more.

$ a'' = a'q + b'q + a'p $
$ b'' = b'p + a'q $

Substitute for $a’$ and $b’$ and rearrange

$ a'' = \left( aq + bq + ap \right) q + \left( bp + aq \right) q + \left( aq + bq + ap \right) p $
$ = ap^2 + bq^2 + 2aq^2 + 2apq + 2bpq $
$ = a \left( 2q^2 + p^2 + 2pq \right) + b \left( q^2 + 2pq \right) $
$ = a \left( q^2 + 2pq \right) + a \left( p^2 + q^2 \right) + b \left( q^2 + 2pq \right) $
$ = a \left( q^2 + 2pq \right) + b \left( q^2 + 2pq \right) + a \left( p^2 + q^2 \right) $
$ b'' = b'p + a'q $
$ = \left( bp + aq \right)p + \left( aq + bq + ap \right)q $
$ = bp^2 + apq + aq^2 + bq^2 + apq $
$ = b\left( p^2 + q^2 \right) + a\left( q^2 + 2pq \right) $

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$</span> and $q’ = q^2 + 2pq$.