The Fibonacci numbers are the sequence , and satisfy the recurrence . They also have a beautiful formula,
This seemingly complicated formula actually has a very simple explanation.
Consider the set of number sequences of the form that satisfy the recurrence . I call the set “” because it turns out to form a vector space. That is, given any two sequences and in , their sum satisfies the same Fibonacci-style recurrence as they do, as does any scalar multiple of .
Notice that is not, however, a very complicated vector space. Because each number sequence in satisfies the Fibonacci-recurrence, each number sequence is entirely determined by its first two entries. Consequently, has dimension two.
If you look at the first few terms of the Fibonacci numbers, you might notice that they seem to grow at a roughly exponential rate. Consequently, one might hope that has a two basis elements of the form and of the form . Indeed, if did, then we would get for free that, for some constants ,
Fortunately, such and do exist and are easy to find. In order for to satisfy the recurrence , we need that . Applying the quadratic formula, we get values for and ,