sol-1.19.tex

The linear transformation $T_{pq}$ is represented by the matrix
$$
\pmatrix{ p + q & q \cr 
          q     & p }\hbox{,}
$$
therefore its square $T_{pq}^2$ is represented by the matrix
$$
\pmatrix{ p + q & q \cr 
          q     & p }^2 = \pmatrix{ (p^2 + q^2) + (q^2 + 2pq) & q^2 + 2pq \cr 
                                    q^2 + 2pq                 & p^2 + q^2 } = \pmatrix{p' + q' & q' \cr
                                                                                       q'      & p' }\hbox{,}
$$
which is also the matrix representing the linear transformation $T_{p'q'}$, with $p' = p^2 + q^2$ and $q' = 2pq + q^2$.
The procedure to compute $\Fib(n)$ becomes
\begtt\scm
(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))
\endtt