SICP-2nd-Edition-Exercise-1.13

From Boozled

Jump to: navigation, search

Contents

Exercise 1.13 From SICP

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

Hint: Let \psi = \frac{ \left( 1 - \sqrt{5} \right)}{2}. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = \frac{ \left( \psi^n - \phi^n \right)}{\sqrt{5}}

Attempt

This is a work in progress at the moment.


This question has two parts that could be separate problems.

  • Prove by induction that Fib(n) = \frac{ \left( \psi^n - \phi^n \right)}{\sqrt{5}} where \psi = \frac{ \left( 1 - \sqrt{5} \right)}{2}
  • Prove that Fib(n) is the closest integer to \frac{\phi^n}{\sqrt{5}}


Part 1

Starting with the induction problem first...

P(n) = \frac{ \left( \psi^n - \phi^n \right)}{\sqrt{5}}
P(1) = \frac{ \left( \psi^1 - \phi^1 \right)}{\sqrt{5}}
P(1) = \frac{\frac{ \left( 1 - \sqrt{5} \right)}{2} - \frac{ \left(1 + \sqrt{5} \right)}{2}}{\sqrt{5}}
P(1) = \frac{\frac{ \left( 1 - \sqrt{5} \right) - \left(1 + \sqrt{5} \right)}{2}}{\sqrt{5}}
P(1) = \frac{\sqrt{5}}{\sqrt{5}} = 1


Inductive step is to assume P(k) is true ie

P(k) = \frac{ \left( \psi^k - \phi^k \right)}{\sqrt{5}}


From our definition of the Fibonacci sequence we have.

Fib(n) = Fib(n − 1) + Fib(n − 2)

and

Fib(n + 1) = Fib(n) + Fib(n − 1)

Therefore

P(k+1) = \frac{ \left( \psi^k - \phi^k \right)}{\sqrt{5}} + \frac{ \left( \psi^\left(k-1\right) - \phi^\left(k-1\right) \right)}{\sqrt{5}}

P(k+1) = \frac{ \left( \psi^k - \phi^k \right) + \left( \psi^\left(k-1\right) - \phi^\left(k-1\right) \right)}{\sqrt{5}}


P(k+1) = \frac{ \psi^k + \psi^\left(k-1\right) - \phi^k - \phi^\left(k-1\right) }{\sqrt{5}}


P(k+1) = \frac{ \psi\psi^\left(k-1\right) + \psi^\left(k-1\right) - \phi\phi^\left(k\right) - \phi^\left(k-1\right) }{\sqrt{5}}

Minor Step:

\psi\psi^\left(k-1\right) + \psi^\left(k-1\right) = \psi^\left(k-1\right)\left(\psi + 1\right)

P(k+1) = \frac{ \psi^\left(k-1\right)\left(\psi + 1\right) - \phi^\left(k-1\right)\left(\phi + 1\right) }{\sqrt{5}}

(Section 1.2.2) also contains the following definition.

Sorry about the change in symbols. Something to do with mediawiki

ψ2 = ψ + 1

Using this we get:

P(k+1) = \frac{ \psi^\left(k-1\right)\psi^2 - \phi^\left(k-1\right)\phi^2 }{\sqrt{5}}

P(k+1) = \frac{ \psi^\left(k-1+2\right) - \phi^\left(k-1+2\right) }{\sqrt{5}}

P(k+1) = \frac{ \psi^\left(k+1\right) - \phi^\left(k+1\right) }{\sqrt{5}}

Part 2

The second part of the question asks us to prove that Fib(n) is the closest integer to \frac{\phi^n}{\sqrt{5}}

To be the closes integer we must use some sort of rounding algorithm. What they are asking us to do is prove.

\left|Fib(n) - \frac{\phi^n}{\sqrt{5}}\right| < \frac{1}{2}

We have already proved the following:

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

So does the following hold:


\left| \frac{ \left( \psi^n - \phi^n \right)}{\sqrt{5}} - \frac{\phi^n}{\sqrt{5}}\right| < \frac{1}{2}


\left| \frac{\psi^n}{\sqrt{5}}\right| < \frac{1}{2}


\frac{\left| \psi^n\right| }{\sqrt{5}}< \frac{1}{2}


\left| \psi^n\right| < \frac{\sqrt{5}}{2}


\left| \frac{ \left( 1 - \sqrt{5} \right)^n}{2^n} \right| < \frac{\sqrt{5}}{2}


We can split this problem up a bit.


\left| \left( 1 - \sqrt{5} \right)^n \right| < 2^n


because


\left| 1 - \sqrt{5} \right| < 2


therefore

\lim_{n \to \infty}\left| \left( \frac{1 - \sqrt{5}}{2} \right)^n \right| = 0

so we know that eventually for sufficiently large n


\left| \frac{ \left( 1 - \sqrt{5} \right)^n}{2^n} \right| < \frac{\sqrt{5}}{2}


holds. If we start to plug in numbers


n \left| \frac{ \left( 1 - \sqrt{5} \right)^n}{2^n} \right| \frac{\left| \frac{ \left( 1 - \sqrt{5} \right)^n}{2^n} \right|}{\sqrt{5}}
1 0.6180 0.276
2 0.382 0.171
3 0.236 0.105


We will see that

\left| \frac{ \left( 1 - \sqrt{5} \right)^n}{2^n} \right| < \frac{\sqrt{5}}{2} for all n \in \{ 1, 2, \ldots \};

Parent Course

6.001_Structure_and_Interpretation_of_Computer_Programs

Further Reading

Induction

Fibonacci

Rounding

Retrieved from "http://www.boozled.org/wiki/index.php/SICP-2nd-Edition-Exercise-1.13"
Personal tools