# Justin Does SICP

**URL:** <https://discuss.criticalfallibilism.com/t/justin-does-sicp/96>\
**Category:** Friendly\
**Tags:** learning, coding\
**Created:** [May 15, 2021, 1:34am UTC](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96 "2021-05-15T01:34:56Z")\
**Posts on this page:** 1\
**Showing post:** 52

<div class="post-metadata">

**Author:** ![Max](https://discuss.criticalfallibilism.com/user_avatar/discuss.criticalfallibilism.com/max/32/97_2.png) [@Max](https://discuss.criticalfallibilism.com/u/Max)\
**Post date:** [May 27, 2021, 10:50pm UTC](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96/52 "2021-05-27T22:50:27Z")

</div>

> [@JustinCEO](#):
>
> is it even a coding exercise at all? it seems like they’re asking for more of a math proof

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

> [@JustinCEO](#):
>
> Also, what do u actually need to know math-wise to solve 1.13

[quality-of-life link back up to 1.13](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96/41)

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.

---

_[View the full topic](https://discuss.criticalfallibilism.com/t/justin-does-sicp/96)._