SICP Exercise 1.13 – Fun with fibonacci

Exercise 1.13 is really interesting, for 'break out the algebra, oooh Fibonacci!' values of interesting, anyway. I had loads of fun with this, having only a passing awareness of the Fibonacci numbers. By the time I had satisfied myself that I understood the question and could venture an answer of my own, I had been on a fascinating journey through the mathematics of Fibonacci numbers and the Golden Ratio. Anyway, on with the exercise.

Prove that $$Fib(n)$$ is the closest integer to $$\phi^n / \sqrt{5}$$, where $$\phi = (1+\sqrt{5})/2$$.

Hint: Let $$\psi = (1-\sqrt{5})/2$$. Use induction and the definition of the Fibbonaci numbers (see section 1.22) to prove that $$Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$$.

Here's the given definition of the Fib function :

2, 3, 5, 8. Who do do we appreciate ?

$$Fib(n) = \begin{cases} 0 & n = 0\\ 1 & n = 1\\ Fib(n-1) + Fib(n-2) & \text{otherwise} \end{cases}$$

We're also given $$\phi = \frac{\left(1 + \sqrt{5} \right)}{ 2 } \approx 1.6180$$ and $$\phi^2 = \phi + 1$$.

We'll start by proving out the theorem from the hint, and see where we get.

Theorem 1.
$$Fib(n) = \frac{ \phi^n - \psi^n }{\sqrt{5}}$$

Base Cases.

\begin{align*} Fib(0) = 0 = \frac{ \phi^0 - \psi^0 }{ \sqrt{ 5 } } = \frac{ 1 - 1}{ \sqrt{5} } = 0 \\ Fib(1) = 1 = \frac{ \phi^1 - \psi^1 }{ \sqrt{ 5 } } = \frac{ \phi - \psi }{ \sqrt { 5 } } = \frac{ \sqrt{5} }{ \sqrt{ 5 } } = 1 \end{align*}

Induction Step.

There are a couple of ways to approach this step, probably the single simplest is to note that both $$\phi$$ and $$\psi$$ have powers that satisfy the Fibonacci recurrence, which is to say that :

$$\phi^n = \phi^{n-1} + \phi^{n-2}$$ $$\psi^n = \psi^{n-1} + \psi^{n-2}$$

Taking that as a given we can simply do this :

\begin{align*} Fib(n-1) + Fib(n-2) = \frac{ \left( \phi^{n-1} - \psi^{n-1} \right) + \left( \phi^{n-2} - \psi^{n-2} \right)}{\sqrt{5}} \\ = \frac{ \left( \phi^{n-1} + \phi^{n-2} \right) - \left(\psi^{n-1} + \psi^{n-2} \right) }{\sqrt{5}} \\ = \frac{\phi^n - \psi^n}{\sqrt{5}} \quad \quad \square \end{align*}

Neat, huh ? "But wait!", I hear you cry, "That's a very short proof and everything, especially given the lengths of some answers to this exercise, but it rests on an assertion you got off Wikipedia and haven't proved! That's cheating!"

And you've got me there. To get to Q.E.D without relying on the assertion, we note that the Golden Ratio has the property $$\phi^2 = \phi + 1$$ given in section 1.22 and we note that $$\psi^2 = \psi + 1$$ is also the case because they're the postive and negative roots of the polynomial $$\phi^2 - \phi - 1 = 0$$. Given which, we can do an induction thusly :

\begin{align*} Fib(n-1) + Fib(n-2) = \frac{ \left( \phi^{n-1} - \psi^{n-1} \right) + \left( \phi^{n-2} - \psi^{n-2} \right)}{\sqrt{5}} \\ = \frac{ \left( \phi^{n-1} + \phi^{n-2} \right) - \left(\psi^{n-1} + \psi^{n-2} \right) }{\sqrt{5}} \\ = \frac{ \left[\left(\phi+1\right)\phi^{n-2}\right] - \left[ \left(\psi+1\right)\psi^{n-2} \right]}{\sqrt{5}} \\ = \frac{ \left[\left(\phi^2\right)\phi^{n-2}\right] - \left[ \left(\psi^2\right)\psi^{n-2} \right]}{\sqrt{5}}\\ = \frac{\phi^n - \psi^n}{\sqrt{5}} \quad \quad \square \end{align*}

Not only does that get us to Q.E.D without relying on an unproven assertion about reccurrence raltions, it also actually proves the relation. Well, at any rate, the proofs drop out of it :

$$\phi^n = \phi^{n-1} + \phi^{n-2} = \left(\phi+1\right )\phi^{n-2} = \left(\phi^2\right)\phi^{n-2} = \phi^n\\ \psi^n = \psi^{n-1} + \psi^{n-2} = \left(\psi+1\right )\psi^{n-2} = \left(\psi^2\right)\psi^{n-2} = \psi^n$$

Smashing. We've proved three things before breakfast and we're not even done yet.

Since we now know that is the case that

$$Fib(n) = \frac{ \phi^n - \psi^n }{\sqrt{5}}$$

We can state that the relationship between $$Fib(n)$$ and $$\phi^n / \sqrt{5}$$ looks like this :

$$\left| Fib(n) \quad - \quad \frac{\phi^n}{\sqrt{5}} \right| \quad = \quad \left| \frac{ \psi^n }{ \sqrt{5}} \right|$$

Clearly as $$n$$ gets really big, $$\psi^n$$ is going to get really small, so $$\phi^n/\sqrt{5}$$ is definitely a good approximation to $$Fib(n)$$, but what about the "closest integer" ? How are we to define that ? Let's throw caution to the wind and decide that it means

Theorem 2.

$$\left| Fib(n) \quad - \quad \frac{\phi^n}{\sqrt{5}} \right| \quad = \quad \left| \frac{ \psi^n }{ \sqrt{5}} \right| \quad \lt \quad \frac{1}{2}$$

Because if we used $$\leq$$ we could have two equidistant integers, and that doesn't fulfil "closest". Can we stand that up ? Let's look at some values :

 $$n$$ $$\psi^n$$ $$\left|\frac{\psi^n }{\sqrt{5}} \right|$$ $$0$$ $$1$$ $$0.44721...$$ $$1$$ $$\psi$$ $$0.27639...$$ $$...$$ $$...$$ $$...$$

Excellent, $$\left|\frac{\psi^n }{\sqrt{5}} \right|$$ starts out $$\lt \frac{1}{2}$$, and it isn't going to get any bigger.

So yes, since $$\left|\frac{\psi^n }{\sqrt{5}} \right| \lt \frac{1}{2}$$ for $$n \geq 0$$ it follows that $$Fib(n)$$ is indeed the closest integer to $$\frac{ \phi^n}{\sqrt{5}} \quad \square$$.

However, since we've proved that, but not tested it, how about some code to look at the numbers ?

And some results* :

 $$n$$ (fib n) (golden-fib n) (closed-fib n) (psi-n-root-5 n) $$0$$ $$0$$ $$0.4472135955$$ $$0.0$$ $$0.4472135955$$ $$1$$ $$1$$ $$0.72360679775$$ $$1.0$$ $$0.27639320225$$ $$2$$ $$1$$ $$1.17082039325$$ $$1.0$$ $$0.17082039325$$ $$3$$ $$2$$ $$1.894427191$$ $$2.0$$ $$0.105572809$$ $$4$$ $$3$$ $$3.06524758425$$ $$3.0$$ $$0.0652475842499$$ $$5$$ $$5$$ $$4.95967477525$$ $$5.0$$ $$0.0403252247502$$ $$6$$ $$8$$ $$8.0249223595$$ $$8.0$$ $$0.0249223594996$$ $$7$$ $$13$$ $$12.9845971347$$ $$13.0$$ $$0.0154028652506$$ $$8$$ $$21$$ $$21.0095194942$$ $$21.0$$ $$0.00951949424901$$ $$9$$ $$34$$ $$33.994116629$$ $$34.0$$ $$0.0058833710016$$ $$10$$ $$55$$ $$55.0036361232$$ $$55.0$$ $$0.00363612324741$$ $$11$$ $$89$$ $$88.9977527522$$ $$89.0$$ $$0.00224724775419$$ $$12$$ $$144$$ $$144.001388875$$ $$144.0$$ $$0.00138887549323$$ $$13$$ $$233$$ $$232.999141628$$ $$233.0$$ $$0.000858372260957$$ $$14$$ $$377$$ $$377.000530503$$ $$377.0$$ $$0.000530503232271$$ $$15$$ $$610$$ $$609.999672131$$ $$610.0$$ $$0.000327869028685$$ $$16$$ $$987$$ $$987.000202634$$ $$987.0$$ $$0.000202634203586$$ $$17$$ $$1597$$ $$1596.99987477$$ $$1597.0$$ $$0.000125234825099$$ $$18$$ $$2584$$ $$2584.0000774$$ $$2584.0$$ $$7.73993784866e-05$$ $$19$$ $$4181$$ $$4180.99995216$$ $$4181.0$$ $$4.78354466128e-05$$ * I actually used a python script to generate the above table. as I haven't got quite so handy with Scheme yet and I was too lazy to type all the table HTML, but the results are within a seriously insignificant distance of one another, on the order of .00000000002 or thereabouts.

SICP Exercise 1.12 – Pascal’s triangle recursively

Exercise 1.12. The following pattern of numbers is called Pascal's triangle.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

It took me a few minutes to grok this one, it helped to draw the triangle like this :

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 

Which makes the "two numbers above" a bit clearer in terms of their actual relative positions. Once we've done that it is easy to see that :

$$P(col,row) = \begin{cases} 1 & col = 0 \\ 1 & col = row \\ P(row - 1, col - 1) + P(row - 1, col) & \text{otherwise} \end{cases}$$

Which translates nice and easy into the Scheme function :

N.B though that since we do absolutely no sanity checking on the input, it is easy to get garbage output, or even to end up with an infinite recursion. So while this is technically a correct answer, it lacks a certain rigour.

Built With Bootstrap