Justin Does SICP

No. It’s like maybe late high-school advanced (like calculus) maths level.

quality-of-life link back up to 1.13

Not that much really. The problem tells you to use induction so you start with evaluating the base case (n=1) for Fib(n) = (\phi^n - \psi^n)/\sqrt{5}. Since we need to use the definition Fib(n) = Fib(n-1) + Fib(n-2) we probably need a 2nd base case too, for n=2. Then the goal is to show that the formula works for some n=k assuming that it already works for n=k-1 and n=k-2. I’d lay that out like:

Goal, show (\phi^{k-1} - \psi^{k-1})/\sqrt{5} + (\phi^{k-2} - \psi^{k-2})/\sqrt{5} = (\phi^k - \psi^k)/\sqrt{5}

\begin{aligned} LHS & = \text{<some algebra here>} \\ & = \dots \\ & = RHS \; \blacksquare \end{aligned}

once you show that the base cases work, and that the case n=k works provided that n=k-1 and n=k-2 work, then you’re done with the proof by induction (because if it works for n \in \{1,2\} then it must work for n=3, so it must also work for n=4, … etc).

The last bit of the exercise (which is actually the first sentence) is to show that Fib(n) is the closest integer to \phi^n/\sqrt{5}. Since we know Fib(n) = (\phi^n - \psi^n)/\sqrt{5}, one way to do that is show that -0.5 \le \psi^n/\sqrt{5} \le 0.5 which is fairly straight forward once you write it out. Note that \lim_{n \to \infty} \psi^n = 0 as |\psi| < 1.