Golden ratio and Fibonacci


I’m currently doing a course on linear algebra, and while working on a hand-in, I discovered this neat proof that the Fibonacci sequence grows exponentially.

Definition: Define two sequences:

  1. a_1 = 1, a_2 = 3, \text{ and } a_n = a_{n-1} + a_{n-2} \text{ for } n>2
  2. b_1 = 1, b_2 = 1, \text{ and } b_n = b_{n-1} + b_{n-2} \text{ for } n>2

Notice that b corresponds to the Fibonacci sequence, and a corresponds to the Lucas numbers, first index truncated.

Lemma 1: For all k>0

  1. a_k = \frac{1}{2} \left ( a_{k-1} + 5\cdot b_{k-1} \right )
  2. b_k = \frac{1}{2} \left ( a_{k-1} + b_{k-1} \right )

Proof. Shown only for 1.1, the proof is similar for 1.2. Proven using strong induction on k.

  • Base-case: 
    Notice that \frac{1}{2} \left ( a_{0} + 5\cdot b_{0} \right ) = \frac{1}{2} \left ( 1 + 5\cdot 1 \right ) = \frac{1}{2} \left ( 6 \right ) = 3 = a_1.
    Which is what we wanted to show.
  • Induction: 
    We see a_k = a_{k-1} + a_{k-2}, by definition.
    We apply the induction hypothesis on k-1, and k-2 to get: a_k = \frac{1}{2} \left ( a_{k-2} + 5\cdot b_{k-2} \right ) + \frac{1}{2} \left ( a_{k-3} + 5\cdot b_{k-3} \right ). We use the definition of a_k and b_k, and get
    a_k = \frac{1}{2} \left ( a_{k-1} + 5\cdot b_{k-1} \right ). Which is what we wanted to show. \blacksquare.

Lemma 2: For all k>0\phi^k = \frac{1}{2} a_k + \frac{1}{2} b_k \cdot \sqrt{5}.

Proof. We prove this lemma using induction on k.

  • Base-case:
    We see that, \frac{1}{2} a_1 + \frac{1}{2} b_1 \cdot \sqrt{5} = \frac{1}{2} 1 + \frac{1}{2} 1 \cdot \sqrt{5} = \frac{1}{2} \left(1 + \sqrt{5} \right) = \phi. Which is what we wanted to show.
  • Induction step:
    We get \phi^k = \phi \cdot \phi^{k-1} = \frac{1}{2}(1+\sqrt{5})\cdot \left( \frac{1}{2} a_{k-1} + \frac{1}{2} b_{k-1} \cdot \sqrt{5} \right), using the induction hypothesis. Multiplying, we get \phi^k = \frac{1}{2} \left ( \frac{1}{2} \left ( a_{k-1} + 5 b_{k-1} \right ) \right ) + \frac{1}{2} \left ( \frac{1}{2} \left ( a_{k-1} + b_{k-1} \right ) \right ) \cdot \sqrt{5}. Using lemma 2, we find \phi^k = \frac{1}{2} a_k + \frac{1}{2} b_k \cdot \sqrt{5}, which is what we wanted to show. \blacksquare.

Now for the interesting part of this article:

Theorem: b_n = \Theta(\phi^n).

Proof. We split the proof into two parts; first proving that b_n = O(\phi^n), then proving b_n = \Omega(\phi^n).

  • b_n = \Omega(\phi^n).
    We see that \phi^n < \frac{1}{2} a_n \cdot \sqrt{5} + \frac{1}{2} b_n \cdot \sqrt{5}, because of lemma 2. Because of lemma 1.2, we have b_n = \frac{1}{2} a_n + \frac{1}{2} b_n, so we get \phi^n < b_{n+1} \cdot \sqrt{5}. This implies that b_n = \Omega(\phi^n).
  • b_n = O(\phi^n).
    We see that \phi^n > \frac{1}{2} b_n because of lemma 2, which implies that b_n = O(\phi^n).

Because b_n = O(\phi^n), and b_n = \Omega(\phi^n), we have b_n = \Theta(\phi^n). That is, the Fibonacci sequence grows exponentially, with base \phi. \blacksquare.

Advertisements

One thought on “Golden ratio and Fibonacci

Comment on this article

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s