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:
Notice that corresponds to the Fibonacci sequence, and corresponds to the Lucas numbers, first index truncated.
Lemma 1: For all
Proof. Shown only for 1.1, the proof is similar for 1.2. Proven using strong induction on .
Notice that .
Which is what we wanted to show.
We see , by definition.
We apply the induction hypothesis on , and to get: . We use the definition of and , and get
. Which is what we wanted to show. .
Lemma 2: For all , .
Proof. We prove this lemma using induction on .
We see that, . Which is what we wanted to show.
- Induction step:
We get , using the induction hypothesis. Multiplying, we get . Using lemma 2, we find , which is what we wanted to show. .
Now for the interesting part of this article:
Proof. We split the proof into two parts; first proving that , then proving .
We see that , because of lemma 2. Because of lemma 1.2, we have , so we get . This implies that .
We see that because of lemma 2, which implies that .
Because , and , we have . That is, the Fibonacci sequence grows exponentially, with base . .