# 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$.

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

## One thought on “Golden ratio and Fibonacci”

1. Anonymous says:

Interesting article! You are very intelligent..