\(\newcommand{\pb}[0]{\overline{\phi}\vphantom{\phi}}\) \(\newcommand{\cb}[0]{\overline{C}\vphantom{C}}\) \(\newcommand{\pbn}[1]{\pb\vphantom{\phi}^{#1}}\)
The Fibonacci Sequence, Lucas Numbers, and the Golden Ratio#
Fibonacci Sequence#
The Fibonacci sequence, aka Fibonacci numbers, is simple enough to be taught in primary schools. Its first few values are:
See that after the two \(1\)s at the beginning, each value is the sum of the two values before it. More formally, the sequence is defined recursively by setting the first two elements of the sequence equal to \(1\) and then applying the rule that each subsequent element is equal to the sum of its two immediate predecessors:
Let’s calculate the 15th Fibonacci number with a simple Python code.
from sympy import *
from IPython.display import Markdown, Math
n = 15
def Fib1(n):
if n < 3:
return 1
else:
Fim2 = 1 # i-2 Fibonacci number
Fim1 = 1 # i-1 Fibonacci number
for i in range(3,n+1):
Fi = Fim2 + Fim1
Fim2 = Fim1
Fim1 = Fi
return Fi
display(Math(str(Fib1(n))))
display(Markdown("The first 20 values in the Fibonacci sequence:"))
vals = [str(Fib1(i)) for i in range(1,20)]
display(Math(', '.join(vals)))
The first 20 values in the Fibonacci sequence:
Fibonacci Sequence for Negative Indices#
The Fib1() function in the code above only delivers valid results for counting numbers \(1, 2, 3...\) Notice that the sequence definition says nothing about a zeroth Fibonacci number \(F_0\) or negatively indexed Fibonacci numbers, e.g. \(F_{-1}\) or \( F_{-5}\). However, the sequence can be extended to include indices below \(1\): We may simply stipulate that the Fibonacci recursion equation also applies to those lower indices. Note that the recursion equation \( F_n = F_{n-1} + F_{n-2} \) can be solved for \(F_{n-2}\), yielding: \( F_{n-2} = F_{n} - F_{n-1} .\) One might prefer to reindex the equation so it reads \( F_{n} = F_{n+2} - F_{n+1} .\)
The equation in its original form said, “Each Fibonacci number is the sum of its two immediate predecessors”; Now the rearranged equation illustrates also that “Each Fibonacci number is the difference of its two immediate successors”. We may apply the equation to calculate values for \(F_0, F_{-1}, F_{-2},\) etc. as far as we please.
Let’s use a function that calculates Fibonacci numbers for any integer index:
n=-10
def Fib2(n):
if n > 0:
return Fib1(n)
else:
Fip2 = 1
Fip1 = 1
for i in range(0,-n+1):
Fi = Fip2 - Fip1
Fip2 = Fip1
Fip1 = Fi
return Fi
display(Math(str(Fib2(n))))
We find that \(F_{-10} = -F_{10}\). A general formula that relates positively and negatively indexed Fibonacci numbers is \(F_{-n}=(-1)^{n+1} F_n .\) In words, the negatively indexed Fibonacci numbers are equal in magnitude to their positively indexed counterparts but alternating in sign. We also find that \(F_0=0\).
display(Markdown("The Fibonacci numbers indexed from -5 to 5 are:"))
vals = [str(Fib2(i)) for i in range(-5,6)]
display(Math(', '.join(vals)))
The Fibonacci numbers indexed from -5 to 5 are:
The Lucas Sequence#
A sequence which is closely related to the Fibonacci sequence is the Lucas sequence \(L_n\). (Lucas is a French name and the s is silent). The Lucas sequence is also known as the Lucas numbers. It can be defined similarly to the Fibonacci sequence:
Lucas Sequence First Definition#
The definition differs only in the second starting value which is \(3\) instead of \(1\).
An equivalent definition gives the Lucas sequence in terms of Fibonacci:
Lucas Sequence Second Definition#
The second definition is can be implemented in code trivially since we already have a Fibonacci function.
def Lucas2(n):
return Fib2(n-1) + Fib2(n+1)
display(Markdown("The Lucas numbers indexed from -5 to 5 are:"))
vals = [str(Lucas2(i)) for i in range(-5,6)]
display(Math(', '.join(vals)))
The Lucas numbers indexed from -5 to 5 are:
Focus on the negatively indexed elements of the two sequences.
display(Math(r'\text{Sequence values indexed from -5 to -1}'))
vals = [str(Fib2(i)) for i in range(-5,0)]
vals = ', '.join(vals)
vals = r'\text{Fibonacci: }' + vals
display(Math(vals))
vals = [str(Lucas2(i)) for i in range(-5,0)]
vals = ', '.join(vals)
vals = r'\text{Lucas: }' + vals
display(Math(vals))
It can be seen that as is the case with Fibonacci numbers, negatively indexed Lucas numbers are alternating in sign. However it is curious that the evenly indexed Fibonacci elements are negative and the oddly index elements are positive whereas with the Lucas numbers the opposite holds.
Again, the equation that relates positively and negatively indexed Fibonacci numbers is \(F_{-n}=(-1)^{n+1} F_n .\)
The analogous formula for Lucas numbers is \(L_{-n}=(-1)^{n} L_n .\)
The Golden Ratio#
The Fibonacci numbers famously exhibit the property that the ratios of successive terms approach \( \phi = \frac{1+\sqrt{5}}{2} \approx 1.61803398875 \), a value known as the golden ratio.
Examples:
\(\frac{F_6}{F_5} = \frac{8}{5} = 1.6\)
\(\frac{F_{11}}{F_{10}}= \frac{89}{55} = 1.6\overline{18}\)
phi = (1 + 5 ** .5)/2
msg = f"Phi is approximately {str(phi)}"
display(Math(r'\text{' + msg + '}'))
msg = r"\frac{F_6}{F_5}" + f" = {str(Fib2(6)/Fib2(5))}"
display(Math(msg))
msg = r"\frac{F_{11}}{F_{10}}" + f" = {str(Fib2(11)/Fib2(10))}"
display(Math(msg))
msg = r"\frac{F_{101}}{F_{100}} = " # F101/F100
msg += r"\frac{" + f"{str(Fib2(101))}" + r"}{" + f"{str(Fib2(100))}" + r"}" # fraction showing values of F101 and F100
msg += f" = {str(Fib2(101)/Fib2(100))}" # value of the fraction F101/F100
display(Math(msg))
It follows that the Fibonacci numbers are approximately proportional to \(\phi^n\). It is possible to directly approximate Fibonacci sequence values using the golden ratio \(\phi\):
n = 10
def Fib3(n): #Fibonacci sequence approximator
return phi ** n/5 ** .5
display(Math(r"F_{" + str(n) + r"} \text{ is }" + str(Fib2(n)) + r"\text{, which is approximately } \phi^{" + str(n) + r"} = " + str(Fib3(n))))
The observations above raise some questions:
Why do the ratios approach \(\phi\)?
Why does \(\sqrt 5\) appear in the approximation formula?
Is there an exact version of the approximation formula?
Firstly, the property that ratios of successive sequence values approach \(\phi\) is not particular to the Fibonacci sequence itself. Let’s define another sequence \(S_n\) which obeys the same recursive property that each element is the sum of the previous two, i.e. \(S_n = S_{n-1} + S_{n-2}\). I’ll randomly choose \(S_1 = 42\) and \(S_2 = 34\). Then \(\frac{S_{n+1}}{S_n} \rightarrow \phi\), or in words, the ratio of successive terms again approaches the golden ratio. In the code output below, see that \(\frac{S_{n+1}}{S_n} \approx \phi\) for large \(n\).
s1 = 42
s2 = 34
def sSequence(n):
sim2 = s1 # S with index i minus 2
sim1 = s2 # S with index i minus 1
for i in range(3, n+1):
si = sim1 + sim2
sim2 = sim1
sim1 = si
return si
msg = f"Phi is approximately {str(phi)}"
display(Math(r'\text{' + msg + '}'))
msg = r"\frac{S_6}{S_5}" + f" = {str(sSequence(6)/sSequence(5))}"
display(Math(msg))
msg = r"\frac{S_{11}}{S_{10}}" + f" = {str(sSequence(11)/sSequence(10))}"
display(Math(msg))
msg = r"\frac{S_{101}}{S_{100}} = " # S101/S100
msg += r"\frac{" + f"{str(sSequence(101))}" + r"}{" + f"{str(sSequence(100))}" + r"}" # fraction showing values of S101 and S100
msg += f" = {str(sSequence(101)/sSequence(100))}" # value of S101/S100
display(Math(msg))
The fact that ratios of successive sequence values approximate \(\phi\) is not specific to the Fibonacci numbers, but is a property of the recurrence relation \(S_n = S_{n-1} + S_{n-2}\).
The recurrence relation is an example of a difference equation, which can be solved using methods similar to linear ordinary differential equations. This will give us a formula that can directly calculate any Fibonacci number and which will incidentally address the three questions posed above. Let’s overview the process step by step.
Write the characteristic equation for \(S_n = S_{n-1} + S_{n-2}\). The since the difference equation is second order, the characteristic equation will be a quadratic polynomial equation.
Find solutions of the characteristic equation \(r_1\) and \(r_2\). These solutions will inform the general solution \(S_n = C \cdot r_1^n + \cb \cdot\overline{r_2}\vphantom{r}^n\).
Use initial values to solve for the constant coefficients \(C\) and \(\cb\).
Now let’s follow these steps to find a formula for calculating Fibonacci numbers!
Binet Formula for Fibonacci Numbers#
Step 1 is to write the characteristic equation, which is done with simple manipulations of the difference equation \(S_n = S_{n-1} + S_ {n-2}\). Replace each instance of \(S\) with \(x\) and change the indices into exponents, yielding the polynomial equation:
\(x^n = x^{n-1} + x^{n-2}\).
Now set \(n = 2\), yielding the characteristic equation:
\(x^2 = x + 1\)
Step 1 is done. The idea is that if a value \(r\) solves this equation, then \(S_n = C \cdot r^n\) will solve the difference equation \(S_n = S_{n-1} + S_{n-2}\) for any constant \(C\). Let’s continue to step 2: Find the solutions of the characteristic equation which will lead to solutions of the difference equation.
# Solving the characteristic polynomial equation x^2 - x - 1 = 0 using the quadratic formula.
# Coefficients
a = 1
b = -1
c = -1
# Discriminant
d = (b**2) - (4*a*c)
# Find the two solutions. I know that the discriminant is 5 > 0, so I'm unaffraid to take its square root.
phi = (-b+d ** .5)/(2*a)
phibar = (-b-d ** .5)/(2*a)
msg = r"\text{One solution is the golden ratio }"
msg += r" \frac{" + str(-b) + r" + \sqrt{" + str(d) + r"}}{" + str(2 * a) + "}." # Calculated phi value in Latex
display(Math(msg))
msg = r"\text{The other solution is the golden ratio's often neglected close relative }"
msg += r"\frac{" + str(-b) + r" - \sqrt{" + str(d) + r"}}{" + str(2 * a) + "}." # Calculated phibar value in Latex
display(Math(msg))
msg = 'The solutions in decimal form are {0} and {1}'.format(phi,phibar)
display(Math(r'\text{' + msg + r'}'))
Skipping the algebra, the solutions of the characteristic equation are the golden ratio \(\phi = \frac{1+\sqrt5}{2}\) and its rational conjugate \(\overline{\phi} = \frac{1-\sqrt5}{2}\).
Step 2 is done. It follows that \(\phi^n = \phi^{n-1} + \phi^{n-2}\) and \(\overline{\phi}\vphantom{\phi}^n = \overline{\phi}\vphantom{\phi}^{n-1} + \overline{\phi}\vphantom{\phi}^{n-2}\), so \(S_n = \phi^n\) and \(S_n = \overline{\phi}\vphantom{\phi}^n\) both solve the difference equation \(S_n = S_{n-1} + S_{n-2}\). An arbitrary linear combination of these two solutions yields the general solution \(S_n = C \cdot \phi^n + \overline{C} \cdot\overline{\phi}\vphantom{\phi}^n\).
To finish, let’s perform step 3. A specific solution for a sequence can be determined by solving for \(C\) and \(\overline{C}\) using initial values. In the case of the Fibonacci sequence, we would like to find values for \(C\) and \(\overline{C}\) so that \(F_n = C \cdot \phi^n + \overline{C} \cdot \overline{\phi}\vphantom{\phi}^n\). So use the known values of \(F_1\) and \(F_2\) to set up a system of linear equations:
$\(\begin{align}
F_1&=1 \text{ so set } C \cdot \phi^1 + \overline{C}\cdot\overline{\phi}\vphantom{\phi}^1=1 \text{ and}\\
F_2&=1 \text{ so set } C \cdot \phi^2 + \overline{C}\cdot\overline{\phi}\vphantom{\phi}^2=1.
\end{align}\)$
In the notation of linear algebra, this equation system may be written as
Python’s sympy can solve this system symbolically and tell us what \(C\) and \(\overline{C}\) are:
# Solve for the coefficients C and Cbar in the formula for Fibonacci numbers.
import sympy as sym
from sympy.matrices import Matrix as mat
phi = (1+sym.sqrt(5))/2
phibar = 1-phi
#initial values of the Fibonacci sequence
S1 = 1
S2 = 1
#Sympy can solve difference equations directly, but I'm builing out the matrix to illustrate.
M = mat([[phi, phibar], [phi ** 2, phibar ** 2]])
b = mat(2, 1, [S1, S2])
c, cbar = sym.symbols(r'C, \overline{C}')
cvec = mat(2, 1, [c, cbar])
display(sym.Eq(cvec, (M.solve(b)).applyfunc(sym.simplify)))
Therefore, the specific solution for Fibonacci numbers is:
\(F_n = \frac{\sqrt5}{5} \phi^n - \frac{\sqrt5}{5} \overline{\phi}\vphantom{\phi}^n \),
which can be rewritten as
\(F_n = \frac{\phi^n - \overline{\phi}\vphantom{\phi}^n}{\sqrt5} \).
This formula is known as the Binet formula, attributed to Jaques Binet who used it in the 19th century.
Note that \(|\overline{\phi}| < 1\) so that \(\overline{\phi}\vphantom{\phi}^n\) goes to \(0\) as \(n\) grows, yielding the approximate formula we saw earlier, \(F_n \approx \frac{\phi^n }{\sqrt5} \). This illustrates why the ratio of successive terms approximates \(\phi\) and why \(\sqrt 5\) appears in the formula.
Let’s repeat the exercise to derive a formula for Lucas numbers:
# Solve for the coefficients C and Cbar in the formula for Lucas numbers.
#initial values of the Lucas sequence
S1 = 1
S2 = 3
b = mat(2, 1, [S1, S2])
display(sym.Eq(cvec, (M.solve(b)).applyfunc(sym.simplify)))
The coefficients for Lucas numbers are both one! The Lucas sequence formula is simply:
$\(L_n = \phi^n + \overline{\phi}\vphantom{\phi}^n .\)$
Just for the sake of my curiosity, I’d like to find the formula for the sequence I invented earlier with \(S_1 = 42\) and \(S_2 = 34\):
# Solve for the coefficients C and Cbar in the formula for Pearson numbers.
#initial values of the sequence
S1 = 42
S2 = 34
b = mat(2, 1, [S1, S2])
display(sym.Eq(cvec, (M.solve(b)).applyfunc(sym.simplify)))
display(sym.Eq(cvec, (M.solve(b)).evalf()))
Note that Sympy can solve difference equations directly:
n = sym.Symbol('n')
f = sym.Function('f')
series = f(n) - f(n-1) - f(n-2)
soln1 = sym.rsolve(series, f(n), {f(1): 1, f(2): 1}) #Solving Fibonacci - Generates Binet's formula in one line.
print('The Binet formula:')
display(soln1)
print('The 20th Fibonacci number using the Binet formula:')
F20 = soln1.subs(n,20).simplify()
display(sym.Eq(soln1.subs(n,20), F20, evaluate=False))
soln2 = sym.rsolve(series, f(n), {f(1): 1, f(2): 3}) #Solving Lucas
print('The 20th Lucas number using the explicit formula:')
L20 = soln2.subs(n,20).simplify()
display(sym.Eq(soln2.subs(n,20), L20, evaluate=False))
The Binet formula:
The 20th Fibonacci number using the Binet formula:
The 20th Lucas number using the explicit formula: