Binet's Formula and the Fibonacci Sequence The Fibonacci Sequence is defined recursively by Fn = Fn–1 + Fn–2, where F0 = 0 and F1 = 1. The first few terms of the sequence are F2 = F1 + F0 = 1 + 0 = 1; F3 = F2 + F1 = 1 + 1 = 2; F4 = F3 + F2 = 2 + 1 = 3; F5 = F4 + F3 = 3 + 2 = 5; F6 = F5 + F4 = 5 + 3 = 8; F7 = F6 + F5 = 8 + 5 = 13; F8 = F7 + F6 = 13 + 8 = 21; F9 = F8 + F7 = 21 + 13 = 34; F10 = F9 + F8 = 34 + 21 = 55; and so on. To determine Fn for arbitrary n, we must know the two preceding terms of Fn in the sequence. The recursive formula requires one to write out all the terms of the sequence in order to find Fn. Is there a short-form formula where we could evaluate it at n and have it generate the nth Fibonacci number? Start with the recursive definition: Fn = Fn–1 + Fn–2. Divide through by Fn–1: (Fn/Fn–1) = 1 + (Fn–2/Fn–1). Let the symbol φ (the Greek letter phi) represent the limit, as n tends to infinity, of Fn / Fn–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 (Fn/Fn–1) = 1 + (Fn–2/Fn–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 = F2 φ + F1; φ3 = F3 φ + F2; φ4 = F4 φ + F3; φ5 = F5 φ + F4; φ6 = F6 φ + F5; and so on. In general, φn = Fn φ + Fn–1; The two roots of φ2 – φ – 1 = 0, which are φ1 = (1 + √5)/2 and φ2 = (1 – √5)/2, both satisfy this form: φ1n = Fn φ1 + Fn–1    and    φ2n = Fn φ2 + Fn–1. Now, subtract: φ1n – φ2n = (Fn φ1 + Fn–1) – (Fn φ2 + Fn–1). The Fn–1 terms cancel. We have: φ1n – φ2n = Fn(φ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: φ1n – φ2n = Fn√5. Isolating Fn, we arrive at Binet's Formula: Fn = (φ1n – φ2n)/√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 reverse-engineers the terms that would precede F0 = 0 and F2 = 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 Gn represent the terms of a recursive sequence, such that Gn = aGn–1 + bGn–2 We assume that G0 = 0 and G1 = 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: An = 2An–1 + An–2, where A0 = 0 and A1 = 1. Terms of this sequence are A2 = 2A1 + A0 = 2(1) + 0 = 2; A3 = 2A2 + A1 = 2(2) + 1 = 5; A4 = 2A3 + A2 = 2(5) + 2 = 12; A5 = 2A4 + A3 = 2(12) + 5 = 29; A6 = 2A5 + A4 = 2(29) + 12 = 70; A7 = 2A6 + A5 = 2(70) + 29 = 169; A8 = 2A7 + A6 = 2(169) + 70 = 408; A9 = 2A8 + A7 = 2(408) + 169 = 985; A10 = 2A9 + A8 = 2(985) + 408 = 2378; and so on. From the recursive rule governing the terms of the sequence, divide through by An–1: (An/An–1) = 2 + (An–2/An–1). Let φ = the limit, as n tends to infinity, of An/An–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 = Anφ + An–1 . The two roots, φ1 = 1 + √2; and φ2 = 1 – √2 both satisfy this formula: φ1n = Anφ1 + An–1 φ2n = Anφ2 + An–1 Subtracting the bottom row from the top gives φ1n – φ2n = An(φ1 – φ2). Furthermore, φ1 – φ2 = (1 + √2) – (1 – √2) = 2√2. Thus, solving for An, we get a formula for the nth term of the sequence An = 2An–1 + An–2: An = (φ1n – φ2n)/(2√2) = [(1 + √2)n – (1 – √2)n]/(2√2). Let's check a couple:   Woo hoo. It works! In general, if Gn = aGn–1 + bGn–2 such that G0 = 0 and G1 = 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: Gn = [((a + √(a2 + 4b))/2)n – ((a – √(a2 + 4b))/2)n]/√(a2 + 4b).   Goof-off Time Now that we have a formula that finds the nth term of a recursive sequence given by Gn = aGn–1 + bGn–2 such that G0 = 0 and G1 = 1, we can use the above formula for negative integers and non-integers, too. In the case of negative integers, it's not that interesting. It just reproduces the terms but in an alternating positive-negative format. In the case of non-integer values for n, cool things happen. For example, let's look at the usual Fibonacci Sequence, Fn = Fn–1 + Fn–2; F0 = 0, F1 = 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: F1/2 = 0.568864481 – 0.351577584i; F3/2 = 0.920442065 + 0.217286897i; F5/2 = 1.489306546 – 0.134290687i; and so on. You can verify that F5/2 = F3/2 + F1/2. In the case of Gn = 2Gn–1 – 3Gn–2; G0 = 0, G1 = 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 An/An–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 Gn = 6Gn–1 – 9Gn–2; G0 = 0, G1 = 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 Gn = 0.4Gn–1 + 0.5Gn–2; G0 = 0, G1 = 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.