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 .

**Base-case: **

Notice that .

Which is what we wanted to show.
**Induction: **

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 .

**Base-case:**

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:

**Theorem: **.

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

### Like this:

Like Loading...

*Related*

Interesting article! You are very intelligent..