Bonus exercise.

Show, by induction, that the haskell function from Lecture 3 computes the n'th fibonacci number.

fib n = iter n (1, 1, 0 , 1)
  where
    iter 0 (a, _, _, _) = a
    iter n (a, b, p, q) =
      if   even n
      then iter (n `div` 2) (a, b, p*p + q*q, 2 * p * q + q * q)
      else iter (n - 1    ) (a * p + b * q, a * q + b * q + b * p, p, q)