Binet's Formula and the Fibonacci Sequence
The Fibonacci Sequence is defined recursively by
F_{n} = F_{n–1} + F_{n–2}, where F_{0} = 0 and F_{1} = 1.
The first few terms of the sequence are
F_{2} = F_{1} + F_{0} = 1 + 0 = 1;
F_{3} = F_{2} + F_{1} = 1 + 1 = 2;
F_{4} = F_{3} + F_{2} = 2 + 1 = 3;
F_{5} = F_{4} + F_{3} = 3 + 2 = 5;
F_{6} = F_{5} + F_{4} = 5 + 3 = 8;
F_{7} = F_{6} + F_{5} = 8 + 5 = 13;
F_{8} = F_{7} + F_{6} = 13 + 8 = 21;
F_{9} = F_{8} + F_{7} = 21 + 13 = 34;
F_{10} = F_{9} + F_{8} = 34 + 21 = 55;
and so on.
To determine F_{n} for arbitrary n, we must know the two preceding terms of F_{n} in the sequence. The recursive formula requires one to write out all the terms of the sequence in order to find F_{n}. Is there a shortform formula where we could evaluate it at n and have it generate the nth Fibonacci number?
Start with the recursive definition:
F_{n} = F_{n–1} + F_{n–2}.
Divide through by F_{n–1}:
(F_{n}/F_{n–1}) = 1 + (F_{n–2}/F_{n–1}).
Let the symbol φ (the Greek letter phi) represent the limit, as n tends to infinity, of F_{n} / F_{n–1}. Roughly speaking, φ represents the limit of the quotient of two consecutive Fibonacci numbers, the larger divided by the smaller. Reciprocating, 1/φ represents the limit of the quotient of two consective Fibonacci numbers, the smaller divided by the larger. Thus, as n increases, the equation
(F_{n}/F_{n–1}) = 1 + (F_{n–2}/F_{n–1}),
can be written, using φ, as:
φ = 1 + (1/φ).
Multiplying through by φ gives
φ^{2} = φ + 1.
Collecting terms to the left side, gives a quadratic in terms of φ:
φ^{2} – φ – 1 = 0.
For reference's sake, let's call this the "φquadratic" corresponding to the given recursive sequence. Using the quadratic formula, we have
φ = (1 ± √5)/2.
Let's denote each solution with subscripts:
φ_{1} = (1 + √5)/2 ≈ 1.6180339887...
φ_{2} = (1 – √5)/2 ≈ –0.6180339887...
Note that both of these numbers satisfies the equation
φ^{2} = φ + 1.
These can be easily verified using a calculator.
Higher Powers of φ
Using this relationship, higher powers of φ can be written by making substitutions and reducing each to a linear equation involving φ. For example,
φ^{3} = φ^{2} φ = (φ + 1) φ = φ^{2} + φ = (φ + 1) + φ = 2φ + 1;
φ^{4} = φ^{3} φ = (2φ + 1) φ = 2φ^{2} + φ = 2(φ + 1) + φ = 3φ + 2;
φ^{5} = φ^{4} φ = (3φ + 2) φ = 3φ^{2} + 2φ = 3(φ + 1) + 2φ = 5φ + 3;
φ^{6} = φ^{5} φ = (5φ + 3) φ = 4φ^{2} + 3φ = 5(φ + 1) + 3φ = 8φ + 5;
and so on.
The coefficients are themselves Fibonacci numbers. The above equations can be summarized as
φ^{2} = F_{2} φ + F_{1};
φ^{3} = F_{3} φ + F_{2};
φ^{4} = F_{4} φ + F_{3};
φ^{5} = F_{5} φ + F_{4};
φ^{6} = F_{6} φ + F_{5};
and so on.
In general,
φ^{n} = F_{n} φ + F_{n–1};
The two roots of φ^{2} – φ – 1 = 0, which are φ_{1} = (1 + √5)/2 and
φ_{2} = (1 – √5)/2, both satisfy this form:
φ_{1}^{n} = F_{n} φ_{1} + F_{n–1} and φ_{2}^{n} = F_{n} φ_{2} + F_{n–1}.
Now, subtract:
φ_{1}^{n} – φ_{2}^{n} = (F_{n} φ_{1} + F_{n–1}) – (F_{n} φ_{2} + F_{n–1}).
The F_{n–1} terms cancel. We have:
φ_{1}^{n} – φ_{2}^{n} = F_{n}(φ_{1} – φ_{2}).
Note that
φ_{1} – φ_{2} = (1 + √5)/2 – (1 – √5)/2 = (1/2 – 1/2) + (√5/2 + √5/2) = √5.
The formula three lines above can be simplied further:
φ_{1}^{n} – φ_{2}^{n} = F_{n}√5.
Isolating F_{n}, we arrive at Binet's Formula:
F_{n} = (φ_{1}^{n} – φ_{2}^{n})/√5 = [((1 + √5)/2)^{n} – ((1 – √5)/2)^{n}]/√5.
This formula can be verified for any positive integer n. Try it on a calculator or in an Excel spreadsheet. Below are three examples of using the formula to determine the 8th, 12th and 30th Fibonacci term: (click to enlarge)
This formula is also valid for n = 0 and for negative integers. It essentially reverseengineers the terms that would precede F_{0} = 0 and F_{2} = 1. For example, F_{–1} = 1, F_{–2} = –1, and so on. Try it by hand first, then verify using the formula.
General Cases
Let G_{n} represent the terms of a recursive sequence, such that
G_{n} = aG_{n–1} + bG_{n–2}
We assume that G_{0} = 0 and G_{1} = 1. Note that when a = 1 and b = 1, this sequence is the familiar Fibonacci Sequence discussed above.
Let's look at the following example:
A_{n} = 2A_{n–1} + A_{n–2}, where A_{0} = 0 and A_{1} = 1.
Terms of this sequence are
A_{2} = 2A_{1} + A_{0} = 2(1) + 0 = 2;
A_{3} = 2A_{2} + A_{1} = 2(2) + 1 = 5;
A_{4} = 2A_{3} + A_{2} = 2(5) + 2 = 12;
A_{5} = 2A_{4} + A_{3} = 2(12) + 5 = 29;
A_{6} = 2A_{5} + A_{4} = 2(29) + 12 = 70;
A_{7} = 2A_{6} + A_{5} = 2(70) + 29 = 169;
A_{8} = 2A_{7} + A_{6} = 2(169) + 70 = 408;
A_{9} = 2A_{8} + A_{7} = 2(408) + 169 = 985;
A_{10} = 2A_{9} + A_{8} = 2(985) + 408 = 2378;
and so on.
From the recursive rule governing the terms of the sequence, divide through by A_{n–1}:
(A_{n}/A_{n–1}) = 2 + (A_{n–2}/A_{n–1}).
Let φ = the limit, as n tends to infinity, of A_{n}/A_{n–1}. Thus, the above equation written in terms of φ is
φ = 2 + (1/φ)
Multiplying by φ gives the square of φ as a linear expression in terms of φ:
φ^{2} = 2φ + 1.
Collecting terms to one side, we obtain this recursive sequence's φquadratic, which is then set to 0:
φ^{2} – 2φ – 1 = 0.
The solutions of this quadratic equation are
φ_{1} = 1 + √2 and φ_{2} = 1 – √2.
So now we find higher powers of φ, and at each instance of encountering φ^{2}, we replace it with 2φ + 1:
φ^{3} = φ^{2} φ = (2φ + 1) φ = 2φ^{2} + φ = 2(2φ + 1) + φ = 5φ + 2;
φ^{4} = φ^{3} φ = (5φ + 2) φ = 5φ^{2} + 2φ = 5(2φ + 1) + 2φ = 12φ + 5;
φ^{5} = φ^{4} φ = (12φ + 5) φ = 12φ^{2} + 5φ = 12(2φ + 1) + 5φ = 29φ + 12;
φ^{6} = φ^{5} φ = (29φ + 12) φ = 29φ^{2} + 12φ = 29(2φ + 1) + 12φ = 70φ + 29;
φ^{7} = φ^{6} φ = (70φ + 29) φ = 70φ^{2} + 29φ = 70(2φ + 1) + 29φ = 169φ + 70;
and so on.
This can be generalized:
φ^{n} = A_{n}φ + A_{n–1} .
The two roots, φ_{1} = 1 + √2; and φ_{2} = 1 – √2 both satisfy this formula:
φ_{1}^{n} = A_{n}φ_{1} + A_{n–1}
φ_{2}^{n} = A_{n}φ_{2} + A_{n–1}
Subtracting the bottom row from the top gives
φ_{1}^{n} – φ_{2}^{n} = A_{n}(φ_{1} – φ_{2}).
Furthermore,
φ_{1} – φ_{2} = (1 + √2) – (1 – √2) = 2√2.
Thus, solving for A_{n}, we get a formula for the nth term of the sequence A_{n} = 2A_{n–1} + A_{n–2}:
A_{n} = (φ_{1}^{n} – φ_{2}^{n})/(2√2) = [(1 + √2)^{n} – (1 – √2)^{n}]/(2√2).
Let's check a couple:
Woo hoo. It works!
In general, if G_{n} = aG_{n–1} + bG_{n–2} such that G_{0} = 0 and G_{1} = 1, then its φquadratic is φ^{2} – aφ – b, and when set to 0, provides two roots that result in the general closed formula for finding the nth term of the given recursive sequence. The formula is:
G_{n} = [((a + √(a^{2} + 4b))/2)^{n} – ((a – √(a^{2} + 4b))/2)^{n}]/√(a^{2} + 4b).
Goofoff Time
Now that we have a formula that finds the nth term of a recursive sequence given by G_{n} = aG_{n–1} + bG_{n–2} such that G_{0} = 0 and G_{1} = 1, we can use the above formula for negative integers and nonintegers, too. In the case of negative integers, it's not that interesting. It just reproduces the terms but in an alternating positivenegative format.
In the case of noninteger values for n, cool things happen. For example, let's look at the usual Fibonacci Sequence, F_{n} = F_{n–1} + F_{n–2}; F_{0} = 0, F_{1} = 1. Because one of the two roots of its φquadratic is negative, using a rational number with an even denominator will result in a complex result. Using a calculator, we get the following:
F_{1/2} = 0.568864481 – 0.351577584i;
F_{3/2} = 0.920442065 + 0.217286897i;
F_{5/2} = 1.489306546 – 0.134290687i;
and so on.
You can verify that F_{5/2} = F_{3/2} + F_{1/2}.
In the case of G_{n} = 2G_{n–1} – 3G_{n–2}; G_{0} = 0, G_{1} = 1, the φquadratic is φ^{2} – 2φ + 3, which results in two complex roots. The terms of this sequence are:
0, 1, 2, 1, –4, –11, –10, 13, 56, 73, –22, –263, –460, –131, 1118, 2629, 1904, –4079, –13870, –15503, 10604, 67717, ... .
Not only are the terms bouncing around chaotically, so are the quotients A_{n}/A_{n–1}. Everything works, in this case, it works peculiarly because of the complex aspect of the roots and how they behave when raised to powers of n.
Try this for G_{n} = 6G_{n–1} – 9G_{n–2}; G_{0} = 0, G_{1} = 1. It's easy to generate terms (you'll get 0, 1, 6, 27, 108, 405, and so on). but the above general formula won't work. Do you see why?
Also, why require that a and b be integers? Try this with G_{n} = 0.4G_{n–1} + 0.5G_{n–2}; G_{0} = 0, G_{1} = 1.
I wouldn't be surprised if this works for quaternions.
By Scott Surgent. Please send feedback or error notification to me at surgent at asu dot edu. Original date Nov 22, 2019, updated Jan 13, 2023.
