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”

Tanner says:

August 10, 2020 at 2:37 am

Cool, I hadn’t seen the general formula with a and b

LikeLiked by 1 person

Share this:

Like this:

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

Leave a Reply Cancel reply