Dan's Thoughts Thinking somewhat carefully

31May/090

Exercise 1.13 of SICP

Exercise 1.13: Prove that Fib(n) is the closest integer to n/5, where \phi = \frac{1 + \sqrt{5}}{2}. Hint: Let \psi = 1-\frac{\sqrt{5}}{2} Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = \frac{\phi^n-\psi^n}{\sqrt5}.

F_n = F_{n-1} + F_{n-2}
F_0 = 0
F_1 = 1

Fn is a linear second-order recurrence with constant coefficients. The characteristic equation for it is: r^2-r-1=0
r = \phi , \psi
This means that the closed form solution is of the form F_n = \alpha\phi^n-\beta\psi^n
The constants \alpha and \beta are determined by the initial conditions bellow.
F_0 = \alpha + \beta = 0
\alpha = -\beta
F_1 = \alpha\phi + \beta\psi = 1
\beta(\psi-\phi)=1
\beta=\frac{1}{\psi-\phi}
\alpha=\frac{-1}{\psi-\phi}
The closed expression has the following form:
F_n = \frac{-\phi^n}{\psi-\phi}-\frac{\psi^n}{\psi-\phi}=\frac{\phi^n-\psi^n}{\sqrt5}

Now that the derivation of the closed form for Fn is done here's the proof by induction.
\phi = \frac{1 + \sqrt{5}}{2}
\psi = \frac{1-\sqrt{5}}{2}
F_n = \frac{\phi^n-\psi^n}{\sqrt5}
F_0 = \frac{\phi^0-\psi^0}{\sqrt5}=0
F_1 = \frac{\phi^1-\psi^1}{\sqrt5}=1
Perform the induction step:
Assume: F_n = \frac{\phi^n-\psi^n}{\sqrt5}
F_{n+1} = F_{n}+F_{n-1} = \frac{\phi^n-\psi^n}{\sqrt5} + \frac{\phi^{n-1}-\psi^{n-1}}{\sqrt5}=\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt5}
F_{n+1} = \frac{\phi^{n-1}(\phi+1)-\psi^{n-1}(\psi+1)}{\sqrt5}
Because \phi^2 = \phi+1
F_{n+1} = \frac{\phi^{n-1}(\phi+1)-\psi^{n-1}(\psi+1)}{\sqrt5}=\frac{\phi^{n+1}-\psi^{n+1}}{\sqrt5}

The proof that F_n = \frac{\phi^n}{\sqrt5} is straightforward.
\psi = \frac{1-\sqrt{5}}{2} = -0.618
\lim_{n \to \infty}\psi^n = 0 for example \psi^{30} \approx 0.0000005374904998555718 and \phi^{30} \approx 1860498
\epsilon = 1-\frac{\phi^{30}-\psi^{30}}{\phi^{30}} \approx 2.8899105330992825 \cdot 10^{-13}
Clearly for n>30 F_n = \frac{\phi^n}{\sqrt5} is a good approximation.

n approx exact epsilon
0 0.4472135955 0.894427191 0.4472135955
1 0.72360679775 0.4472135955 0.27639320225
2 1.17082039325 1.3416407865 0.17082039325
3 1.894427191 1.788854382 0.105572809
4 3.06524758425 3.1304951685 0.0652475842499
5 4.95967477525 4.9193495505 0.0403252247502
6 8.0249223595 8.049844719 0.0249223594996
7 12.9845971347 12.9691942695 0.0154028652506
8 21.0095194942 21.0190389885 0.00951949424901
9 33.994116629 33.988233258 0.00588337100159
Filed under: SICP, lisp, math Leave a comment
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment


Spam protection by WP Captcha-Free

No trackbacks yet.

» «

Pages

Categories

Blogroll

Archive

Meta