Finding the Fibonacci Numbers: A Similar Formula

In this series of posts about the Fibonacci sequence F_n, a very famous sequence of numbers within mathematics, we have just concluded showing how you can take the recursive formula (which uses previous values of F_n to compute the next values) and turn that formula into an exact formula that can skip right over the previous values to any F_n we happen to want to know.

The purpose of this discussion is to show how mathematicians generalize their ideas – by which I mean taking the same idea and applying that idea in as broad a context as possible. And to make things more interesting for my reader – I genuinely don’t think I’ve every derived this formula before. And I am not looking up anything as I do this. But I do go into this expecting a particular type of answer. So, this should serve for my readers as an example of how a mathematician thinks about his work.

Generalizing the Fibonacci Numbers

In order to generalize a concept, we must obtain a deeper understanding of what actually mattered for the problem we were initially dealing with. In order to understand this, it is extremely helpful to summarize our reasoning process for the actual Fibonacci sequence F_n.

Drawing from my previous articles, our basic point was to use the fact that F_n grows roughly like the exponential function \varphi^n to connect the recurrence formula F_{n+1} = F_n + F_{n-1} to the quadratic equation x^2 = x + 1. We then used the ‘largest’ of the two solutions to this quadratic equation to predict the approximate size of F_n, and we used the ‘smallest’ of the two solutions to determine how far off our initial guess was.

Now, the Fibonacci sequence is just a list of numbers generated by the two previous terms in the list. In light of this, it would make sense to ask whether a similar exact formula will work for any sequence that is generated in the same way by the previous two terms using integers. To define this more clearly, choose some random positive whole numbers a, b. Using these, define the sequence G_n by G_0 = 0, G_1 = 1, and G_{n+1} = a G_n + b G_{n-1}. To give an example, if we choose a = 2 and b = 3, then we get a list 0, 1, 2, 7, 20, 61, \dots.

Using the Same Concept

We now apply the same conceptual schema that worked with F_n to G_n to try to come up with a formula for G_n. The conceptual framework of the discussion of F_n transformed the equation F_{n+1} = F_n + F_{n-1} into the equation x^{n+1} = x^n + x^{n-1}, which is then transformed into x^2 = x + 1. Using the same concepts, we might try guessing that G_n is “basically” some exponential, transforming G_{n+1} = a G_n + b G_{n-1} into x^{n+1} = a x^n + b x^{n-1}, which then transforms into x^2 = ax + b.

Our next step for F_n transforms x^2 = x + 1 into x^2 - x - 1 = 0 and uses the quadratic formula to produce the two solutions. The larger of these was \varphi = \dfrac{1 + \sqrt{5}}{2} and the smaller was \psi = \dfrac{1 - \sqrt{5}}{2}. In our new G_n framework, we use instead the quadratic equation x^2 - ax - b = 0, and the quadratic formula gives us the roots \alpha (the larger root) and \beta (the smaller root):

\alpha = \dfrac{a + \sqrt{b^2 - 4a}}{2}

and

\beta = \dfrac{a - \sqrt{b^2 - 4a}}{2}.

The exact formula for F_n was expressed as F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}. We might notice that \sqrt{5} = \varphi - \psi, and that therefore F_n = \dfrac{\varphi^n - \psi^n}{\varphi - \psi}. We might therefore hope that

G_n = \dfrac{\alpha^n - \beta^n}{\alpha - \beta}.

This turns out to be exactly right. See if you can figure out why before moving on and reading the proof!

The Exact Formula

Now that we have developed the relevant concepts and our guess for an exact formula for G_n, we can attempt to prove our exact formula.

Theorem: For any positive integers a, b, the sequence G_n defined by G_0 = 0, G_1 = 1, and G_{n+1} = a G_n + b G_{n-1}, we have

G_n = \dfrac{\alpha^n - \beta^n}{\alpha - \beta}.

Proof: As discussed in a previous proof in this series, we only need to show that the formula \dfrac{\alpha^n - \beta^n}{\alpha - \beta} solves all three components in the statement, and as before it is not difficult to show that the n = 0 and n = 1 cases do give the values of 0 and 1, since \alpha^0 - \beta^0 = 1 - 1 = 0 and \dfrac{\alpha - \beta}{\alpha - \beta} = 1.

Now, we know that \alpha^2 - a\alpha - b = \beta^2 - a \beta - b = 0, since \alpha, \beta are the solutions to the equation x^2 - ax - b = 0. Since you can multiply 0 by anything you want and it will remain zero, we can conclude from this (by multiplying by both \alpha^{n-1} and \beta^{n-1}) that

\alpha^{n+1} - a \alpha^n - b \alpha^{n-1} = \beta^{n+1} - a \beta^n - b \beta^{n-1},

from which we can conclude that

\alpha^{n+1} - \beta^{n+1} = a(\alpha^n - \beta^n) + b(\alpha^{n-1} + \beta^{n-1}).

Dividing both sides of this by \alpha - \beta yields the equation

\dfrac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta} = a \dfrac{\alpha^n - \beta^n}{\alpha - \beta} + b \dfrac{\alpha^{n-1} - \beta^{n-1}}{\alpha - \beta}.

This just is the identity G_{n+1} = aG_n + bG_{n-1}, which was the only piece of the puzzle that was missing. Therefore, the exact formula we have given for G_n is correct.

Here, we now have a nice example of generalizing ideas that we come up with for a specific problem to deal with a broader problem. So, if we ever come across situation with the specific kind of “generational growth pattern” that we saw in the very first post with the rabbits, we will know how to handle it.

One thought on “Finding the Fibonacci Numbers: A Similar Formula

Leave a Reply

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: