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$.