Something more on Fibonacci numbers

Pascal triangle Fibonacci
Image via Wikipedia

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} .

One thought on “Something more on Fibonacci numbers

Comments are closed.