Smatchcube's website 🌍


Exercise 1.19

\[\begin{align} T_{pq}(T_{pq}(a,b))&=T_{pq}(bq+aq+ap,bp+aq)\\&=(q(bp+aq)+q(bq+aq+ap)+p(bq+aq+ap),p(bp+aq)+q(bq+aq+ap))\\&=(bpq+aq^2+bq^2+aq^2+apq+bpq+apq+ap^2,bp^2+apq+bq^2+aq^2+apq)\\&=(b(q^2+2pq)+a(q^2+2pq)+a(p^2+q^2),b(p^2+q^2)+(q^2+2pq))\\&=(bq'+aq'+ap',bp'+aq')\\&=T_{p'q'}(a,b)\end{align}\] With \(p'=p^2+q^2\) and \(q'=q^2+2pq\).

This result leads us to the following clever algorithm to compute the Fibonacci numbers in a logarithmic number of steps: