Something more on Fibonacci numbers

My earlier blog about the Fibonacci series gets a lot of hits, so I thought I would write something more, as clearly there is interest.

Once again this is from “Structure and Interpretation of Computer Programs” (available for free here electronically):

Let $\psi = (1 - \sqrt{5})/2$ and $\phi = (1 + \sqrt{5}/2)$ . Then $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$ .

So $Fib(1) = (\frac{1}{2} +\frac{\sqrt{5}}{2} - \frac{1}{2} + \frac{\sqrt{5}}{2})/\sqrt{5} = 1$ .

(1) $Fib(n) = (\phi^n - \psi^n)/\sqrt{5} = Fib(n - 1) + Fib(n - 2)$

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

(3) Simplifying (2) $Fib(n) = \frac{\phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}}{\sqrt{5}}$

(4) Simplifying further – from (1): $\phi^n - \psi^n = \phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}$

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

(6) We know that $\phi^2 = (\phi + 1)$ so we can restate (5) as $\phi^n - \psi^n = \phi^n - \psi^{n - 2} - \psi^{n - 1}$

So (7) $\psi^n = \psi^{n - 2} + \psi^{n - 1}$

But $\psi^2 = \psi + 1$ also and (7) can be restated as $\psi^n = \psi^{n-2}(\psi + 1) = \psi^{n-2}\psi^2 = \psi^n$

In other words, $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$ .

cartesian product … stuff about computing mostly