Solution to 1.13

[Bobby Moretti]

Hi all,

A couple weeks ago someone asked how to do 1.13. We didn't have time
to go over it during the meeting, but I wrote up a solution to it for
those who are curious. It's very explicit; I tried not to leave
anything out. As a result it's kind of long, but it shouldn't be out
of reach of anyone here, so long as you remember basic algebra.

Also, the exercise's question is kind of overkill: to show that the
algorithm in question has exponential runtime, you really only need to
show that fib(n+1) = C*f(n), where C is some constant greater than
one...

--
Bobby Moretti
mor...@u.washington.edu