In this series of posts about the Fibonacci sequence , 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 to compute the next values) and turn that formula into an exact formula that can skip right over the previous values to any 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 .
Drawing from my previous articles, our basic point was to use the fact that grows roughly like the exponential function to connect the recurrence formula to the quadratic equation . We then used the ‘largest’ of the two solutions to this quadratic equation to predict the approximate size of , 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 . Using these, define the sequence by , and . To give an example, if we choose and , then we get a list .
Using the Same Concept
We now apply the same conceptual schema that worked with to to try to come up with a formula for . The conceptual framework of the discussion of transformed the equation into the equation , which is then transformed into . Using the same concepts, we might try guessing that is “basically” some exponential, transforming into , which then transforms into .
Our next step for transforms into and uses the quadratic formula to produce the two solutions. The larger of these was and the smaller was . In our new framework, we use instead the quadratic equation , and the quadratic formula gives us the roots (the larger root) and (the smaller root):
The exact formula for was expressed as . We might notice that , and that therefore . We might therefore hope that
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 , we can attempt to prove our exact formula.
Theorem: For any positive integers , the sequence defined by , and , we have
Proof: As discussed in a previous proof in this series, we only need to show that the formula solves all three components in the statement, and as before it is not difficult to show that the and cases do give the values of 0 and 1, since and .
Now, we know that , since are the solutions to the equation . Since you can multiply 0 by anything you want and it will remain zero, we can conclude from this (by multiplying by both and ) that
from which we can conclude that
Dividing both sides of this by yields the equation
This just is the identity , which was the only piece of the puzzle that was missing. Therefore, the exact formula we have given for 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.