Fibonacci Sequence Relationships
CatholicMathGuy
07/24/2020
Fibonacci Sequence Relationships
This article will explore interesting (or perhaps, amazing) relationships the Fibonacci sequence (described in the article Description, Mathematics And Other Fun Facts of the Fibonacci Sequence) has with the golden ratio (described in the article Description, Mathematics And Other Fun Facts of the Golden Ratio) and other mathematical powerhouses such as Pascal’s Triangle. The specific topics presented are:
- Fibonacci Sequence Review
- Fibonacci Sequence And The Golden Ratio
- Fibonacci Sequence Ratio Limit Proof
- Fibonacci Sequence And The Golden Ratio Estimate
- Fibonacci Sequence and The Golden Rectangle
- Fibonacci Spiral and The Golden Spiral
- Fibonacci Sequence - Binet’s Formula
- Fibonacci Sequence And Pascal’s Triangle
Fibonacci Sequence Review
First recall that the Fibonacci sequence is defined as
\[ \left\{F_{n}\right\}_{n=1}^{\infty} \]
with \(F_{n} = F_{n-1} + F_{n-2}\) with the initial conditions of \(F_{1} = 1\) and \(F_{2} = 1\) (or sometimes the Fibonacci sequence starts at \(N = 0\), where \(F_{0} = 0\) and \(F_{1} = 1\)). The first 20 terms of the sequence are:
| \(N\) | Fibonacci Number |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
| 11 | 89 |
| 12 | 144 |
| 13 | 233 |
| 14 | 377 |
| 15 | 610 |
| 16 | 987 |
| 17 | 1597 |
| 18 | 2584 |
| 19 | 4181 |
| 20 | 6765 |
Fibonacci Sequence And The Golden Ratio
For a given \(N\), if one was to explore the ratio of this term in the sequence, \(F_{N}\), to the one previous, \(F_{N-1}\) (that is \(F_{N}/F_{N-1}\)), it will not take long to see that this ratio begins to converge as the following output of a Python routine (computeFibRatio) illustrates (with the initial condition of the first ratio set to 1):
## N FibNum Ratio
## 1 1 1.00000000000000
## 2 1 1.00000000000000
## 3 2 2.00000000000000
## 4 3 1.50000000000000
## 5 5 1.66666666666667
## 6 8 1.60000000000000
## 7 13 1.62500000000000
## 8 21 1.61538461538462
## 9 34 1.61904761904762
## 10 55 1.61764705882353
## 11 89 1.61818181818182
## 12 144 1.61797752808989
## 13 233 1.61805555555556
## 14 377 1.61802575107296
## 15 610 1.61803713527851
## 16 987 1.61803278688525
## 17 1597 1.61803444782168
## 18 2584 1.61803381340013
## 19 4181 1.61803405572755
## 20 6765 1.61803396316671
## 21 10946 1.61803399852180
## 22 17711 1.61803398501736
## 23 28657 1.61803399017560
## 24 46368 1.61803398820532
## 25 75025 1.61803398895790
## 26 121393 1.61803398867044
## 27 196418 1.61803398878024
## 28 317811 1.61803398873830
## 29 514229 1.61803398875432
## 30 832040 1.61803398874820
## 31 1346269 1.61803398875054
## 32 2178309 1.61803398874965
## 33 3524578 1.61803398874999
## 34 5702887 1.61803398874986
## 35 9227465 1.61803398874991
## 36 14930352 1.61803398874989
## 37 24157817 1.61803398874990
## 38 39088169 1.61803398874989
## 39 63245986 1.61803398874990
## 40 102334155 1.61803398874989
## 41 165580141 1.61803398874989
## 42 267914296 1.61803398874989
## 43 433494437 1.61803398874989
## 44 701408733 1.61803398874989
## 45 1134903170 1.61803398874989Indeed, as \(N\) gets bigger and bigger the ratio of successive terms, \(F_{N}/F_{N-1}\), converges to (approximately) 1.61803398874989484820. This number is none other than the golden ratio, \(\phi = 1.61803398874989484820\)! Stated mathematically:
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N}}{F_{N-1}} &= 1.61803398874989484820 \\ \lim_{N \to \infty} \frac{F_{N}}{F_{N-1}} &= \phi \end{align} \]
Note: The expression of this ratio \(F_{N}/F_{N-1}\) is sometimes expressed equivalently as \(F_{N+1}/F_{N}\), so equivalently:
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= 1.61803398874989484820 \\ \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= \phi \end{align} \]
Fibonacci Sequence Ratio Limit Proof
The limit of the ratio of successive terms of the Fibonacci sequence was empirically shown above in Fibonacci Sequence And Golden Ratio to be \(\phi\). This section will present a more formal proof of
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= \phi \end{align} \]
Assume that the limit exists and is \(L\). That is
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= L \end{align} \]
Using the fact that \(F_{N+1} = F_{N} + F_{N-1}\):
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= \lim_{N \to \infty} \frac{F_{N} + F_{N-1}}{F_{N}} \\ \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= \lim_{N \to \infty} \left(1 + \frac{F_{N-1}}{F_{N}}\right) \\ \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= 1 + \lim_{N \to \infty} \frac{F_{N-1}}{F_{N}} \\ \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= 1 + \lim_{N \to \infty} \frac{1}{\frac{F_{N}}{F_{N-1}}} \end{align} \]
But since the (assumed) \(\lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} = L\) then so too is \(\lim_{N \to \infty} \frac{F_{N}}{F_{N-1}} = L\). Hence:
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= 1 + \lim_{N \to \infty} \frac{1}{\frac{F_{N}}{F_{N-1}}} \\ L &= 1 + \frac{1}{L} \\ L &= \frac{L + 1}{L} \\ L^{2} &= L + 1 \\ 0 &= L^{2} - L - 1 \end{align} \]
Applying the quadratic formula to \(L^{2} - L - 1 = 0\)
\[ \begin{align} 0 &= L^{2} - L - 1 \\ L &= \frac{-(-1) \pm \sqrt{(-1)^{2} - 4(1)(-1)}}{2(1)} \\ L &= \frac{1 \pm \sqrt{5}}{2} \end{align} \]
As expected, there are two solutions. However, since \(L\) represents the limit of the ratio of two successive terms in the Fibonacci sequence which are always positive, only the positive solution is applicable:
\[ \begin{align} L &= \frac{1 + \sqrt{5}}{2} \end{align} \]
which is exactly \(\phi\). Hence,
\[ \begin{align} \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= \frac{1 + \sqrt{5}}{2} \\ \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} &= \phi \end{align} \]
The conclusion that \(\lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} = \phi\) was predicated on the assumption that the limit of the ratio of two successive terms in the Fibonacci sequence exists. It is necessary to show that the limit does, indeed, exist. To do so one would employ the \(\delta\) - \(\epsilon\) (delta-epsilon) technique. For the purposes here, it will suffice to show empirically that
\[ \left|\frac{F_{N+1}}{F_{N}} - \phi\right| \]
converges to 0 as \(N \to \infty\). The following is the output of the Python routine, computeFibRatio, though now including the deltas between the ratios and \(\phi\), which clearly shows a convergence to zero:
## N FibNum Ratio Delta
## 1 1 1.00000000000000 6.18033988749895e-01
## 2 1 1.00000000000000 6.18033988749895e-01
## 3 2 2.00000000000000 3.81966011250105e-01
## 4 3 1.50000000000000 1.18033988749895e-01
## 5 5 1.66666666666667 4.86326779167718e-02
## 6 8 1.60000000000000 1.80339887498948e-02
## 7 13 1.62500000000000 6.96601125010510e-03
## 8 21 1.61538461538462 2.64937336527948e-03
## 9 34 1.61904761904762 1.01363029772417e-03
## 10 55 1.61764705882353 3.86929926365465e-04
## 11 89 1.61818181818182 1.47829431923263e-04
## 12 144 1.61797752808989 5.64606600073070e-05
## 13 233 1.61805555555556 2.15668056606777e-05
## 14 377 1.61802575107296 8.23767693347577e-06
## 15 610 1.61803713527851 3.14652861965747e-06
## 16 987 1.61803278688525 1.20186464891425e-06
## 17 1597 1.61803444782168 4.59071787028975e-07
## 18 2584 1.61803381340013 1.75349769593325e-07
## 19 4181 1.61803405572755 6.69776591966098e-08
## 20 6765 1.61803396316671 2.55831884565794e-08
## 21 10946 1.61803399852180 9.77190839357434e-09
## 22 17711 1.61803398501736 3.73253694618825e-09
## 23 28657 1.61803399017560 1.42570222294580e-09
## 24 46368 1.61803398820532 5.44569944693762e-10
## 25 75025 1.61803398895790 2.08007167046276e-10
## 26 121393 1.61803398867044 7.94517784896698e-11
## 27 196418 1.61803398878024 3.03477243335237e-11
## 28 317811 1.61803398873830 1.15918386001113e-11
## 29 514229 1.61803398875432 4.42756942220512e-12
## 30 832040 1.61803398874820 1.69131375571396e-12
## 31 1346269 1.61803398875054 6.45927755726916e-13
## 32 2178309 1.61803398874965 2.46691556071710e-13
## 33 3524578 1.61803398874999 9.41469124882133e-14
## 34 5702887 1.61803398874986 3.59712259978551e-14
## 35 9227465 1.61803398874991 1.37667655053519e-14
## 36 14930352 1.61803398874989 5.32907051820075e-15
## 37 24157817 1.61803398874990 1.99840144432528e-15
## 38 39088169 1.61803398874989 8.88178419700125e-16
## 39 63245986 1.61803398874990 2.22044604925031e-16
## 40 102334155 1.61803398874989 2.22044604925031e-16
## 41 165580141 1.61803398874989 0.00000000000000e+00
## 42 267914296 1.61803398874989 0.00000000000000e+00
## 43 433494437 1.61803398874989 0.00000000000000e+00
## 44 701408733 1.61803398874989 0.00000000000000e+00
## 45 1134903170 1.61803398874989 0.00000000000000e+00Fibonacci Sequence And The Golden Ratio Estimate
In the article, Description, Mathematics And Other Fun Facts of the Golden Ratio, it was shown that the golden ratio is indeed an irrational number and can be expressed as the continued fraction
\[ \begin{align} \phi &= 1 + \frac{1}{\phi} \\ \phi &= 1 + \frac{1}{1 + \frac{1}{\phi}} \\ \phi &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\phi}}} \\ \phi &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\dots}}}} \\ \end{align} \]
The expansion of this continued fraction will be of interest to estimate \(\phi\) as the ratio of two numbers. Letting \(\phi = 1\), then the first iteration of the sequence is:
\[ \begin{align} \phi &= 1 + \frac{1}{1} \\ \phi &= 2 \end{align} \]
The second iteration of the sequence is:
\[ \begin{align} \phi &= 1 + \frac{1}{1 + \frac{1}{1}} \\ \phi &= 1 + \frac{1}{2} \\ \phi &= \frac{3}{2} \end{align} \]
The third iteration of the sequence is:
\[ \begin{align} \phi &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}} \\ \phi &= 1 + \frac{1}{1 + \frac{1}{2}} \\ \phi &= 1 + \frac{1}{\frac{3}{2}} \\ \phi &= 1 + \frac{2}{3} \\ \phi &= \frac{5}{3} \end{align} \]
The fourth iteration of the sequence is:
\[ \begin{align} \phi &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}}} \\ \phi &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{2}}} \\ \phi &= 1 + \frac{1}{1 + \frac{1}{\frac{3}{2}}} \\ \phi &= 1 + \frac{1}{1 + \frac{2}{3}} \\ \phi &= 1 + \frac{1}{\frac{5}{3}} \\ \phi &= 1 + \frac{3}{5} \\ \phi &= \frac{8}{5} \end{align} \]
The fifth iteration would produce \(\phi = \frac{13}{8}\), and so on. The sequence of estimates of \(\phi\) as the ratio of two numbers is:
\[ \left\{1,2,\frac{3}{2},\frac{5}{3},\frac{8}{5},\dots\right\} \]
Two interesting things to note. The first is that each successive term in the sequence is \(1 + \frac{1}{x}\) where \(x\) is the previous term. This is consistent with \(\phi = 1 + \frac{1}{\phi}\). But perhaps even more interesting (or amazing!) is that each term in the sequence is the ratio of successive Fibonacci numbers! With each term in the sequence being the ratio \(\frac{F_{N+1}}{F_{N}}\), then as the number of terms in the sequence grows, it is clear that
\[ \phi = \lim_{N \to \infty} \frac{F_{N+1}}{F_{N}} \]
This is consistent with what was presented in Fibonacci Sequence And The Golden Ratio and shown to be true in Fibonacci Sequence Ratio Limit Proof. Again, Amazing!.
Fibonacci Sequence and The Golden Rectangle
In the article, Description, Mathematics And Other Fun Facts of the Golden Ratio, a golden rectangle was defined as a rectangle whose side lengths are in the golden ratio and it was shown how to construct a unit golden rectangle in five easy steps. From the knowledge that the ratio of consecutive Fibonnaci numbers is approximately the golden ratio (\(\phi\)) then any rectangle whose sides are of lengths \(F_{N}\) and \(F_{N+1}\) would also form a golden rectangle. The greater these two consecutive lengths are, the closer the approximation to a true golden rectangle it would be.
It is said that golden rectangles are the most pleasing. As an experiment, here are 10 rectangles where some are constructed with a width of one number in the Fibonacci sequence, \(F_{N}\), and a height with the next number in the sequence, \(F_{N+1}\), or vice versa (i.e., the width being of length \(F_{N+1}\) and the height being of length \(F_{N}\)). Thus these such constructed rectangles approximate golden rectangles. The other rectangles are “normal” rectangles in the sense of there being no relationship between the widths and heights. Which are the most pleasing rectangles to you?
Fibonacci Spiral and The Golden Spiral
In the article, Description, Mathematics And Other Fun Facts of the Fibonacci Sequence, the Fibonacci spiral was defined and was stated to be one form (or approximation) of a golden spiral, which is a logarithmic spiral with a growth factor of \(\phi\), the golden ratio. Since the limit of the ratio of consecutive Fibonnaci numbers is \(\phi\) (the golden ratio), the more Fibonacci squares added, the closer the approximation will be to a true golden spiral.
Fibonacci Sequence - Binet’s Formula
Given the Fibonacci sequence is defined as
\[ \left\{F_{n}\right\}_{n=1}^{\infty} \]
with \(F_{n} = F_{n-1} + F_{n-2}\) the finding of the \(n^{th}\) term in the sequence is a challenge for the sequence is a recurrence relation, which in this case means it is dependent on the two previous terms. A very elegant solution was presented in the article, Description, Mathematics And Other Fun Facts of the Golden Ratio, where the finding of \(F_{n}\) is a matter of exponentiating the matrix \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) to the \(n^{th}\) power and extracting the second element of the first row. This can be done quite efficiently using matrix exponentiation. There is, of course, other ways to compute the \(n^{th}\) term in the Fibonacci sequence (though perhaps less elegant and less efficient). One such way is via Binet’s Formula defined as:
\[ F_{n} = \frac{1}{\sqrt{5}} \left[ \left(\frac{1 + \sqrt{5}}{2}\right)^{N} - \left(\frac{1 - \sqrt{5}}{2}\right)^{N} \right] \]
Upon close inspection of Binet’s formula, one notices that \(\frac{1 + \sqrt{5}}{2} =\phi\). The second term, \(\frac{1 - \sqrt{5}}{2}\), is not only the other solution to the quadratic \(L^{2} - L - 1 = 0\) (see Fibonacci Sequence Ratio Limit Proof) but is the conjugate of \(\frac{1 + \sqrt{5}}{2}\). From this it can be shown that \(\frac{-1}{\phi} = \frac{1 - \sqrt{5}}{2}\) as follows:
\[ \begin{align} \frac{-1}{\phi} &= \frac{-1}{\frac{1 + \sqrt{5}}{2}} \\ \frac{-1}{\phi} &= \frac{-2}{1 + \sqrt{5}} \\ \frac{-1}{\phi} &= \frac{-2(1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} \\ \frac{-1}{\phi} &= \frac{-2(1 - \sqrt{5})}{1 - 5} \\ \frac{-1}{\phi} &= \frac{-2(1 - \sqrt{5})}{-4} \\ \frac{-1}{\phi} &= \frac{1 - \sqrt{5}}{2} \end{align} \]
Using both \(\phi = \frac{1 + \sqrt{5}}{2}\) and \(\frac{-1}{\phi} = \frac{1 - \sqrt{5}}{2}\), Binet’s formula can be expressed as:
\[ \begin{align} F_{n} &= \frac{1}{\sqrt{5}} \left[ \phi^{N} - \left(\frac{-1}{\phi}\right)^{N} \right] \\ F_{n} &= \frac{1}{\sqrt{5}} \left[ \phi^{N} - \frac{(-1)^{N}}{\phi^{N}} \right] \end{align} \]
From this, it is seen that the \(n^{th}\) term in the Fibonacci sequence can be expressed in terms of the golden ratio, \(\phi = \frac{1 + \sqrt{5}}{2}\). Amazing!
Fibonacci Sequence And Pascal’s Triangle
To do justice to Pascal’s Triangle would require (at least) its own article. For the purposes herein, a brief summary will suffice with the specific focus being on the relationship to the Fibonacci sequence.
Pascal’s triangle is (usually) represented as follows (only the first 7 rows are shown, where the rows are counting starting with row 0):
The applicabilities of the triangle in mathematics are numerous; some of the well known include (note: this is far from an exhaustive detailed description but rather just to give a very brief overview; the reader is encouraged to seek out more detailed information):
- Binomial Expansion
- \((a + b)^{n}\): The coefficients of the polynomial expansion correspond to the numbers in the \(n^{th}\) row of the triangle
- For example \((a + b)^{3} = 1 \cdot a^{3} + 3 \cdot a^{2}b + 3 \cdot ab^{2} + 1 \cdot b^{3}\)
- \((a + b)^{n}\): The coefficients of the polynomial expansion correspond to the numbers in the \(n^{th}\) row of the triangle
- Combinatorics
- \({n \choose r}\) (read n choose r): The number of ways to select \(r\) combinations out of \(n\) objects (order does not matter) where \({n \choose r} = \frac{n!}{r!(n-r)!}\) corresponds to the \(r^{th}\) entry in the \(n^{th}\) row of the triangle (the counting of entries in a row starts with 0)
- For example \({4 \choose 2} = \frac{4!}{2!(4-2)!} = 6\). This is the \(2^{nd}\) entry in the \(4^{th}\) row of the triangle
- \({n \choose r}\) (read n choose r): The number of ways to select \(r\) combinations out of \(n\) objects (order does not matter) where \({n \choose r} = \frac{n!}{r!(n-r)!}\) corresponds to the \(r^{th}\) entry in the \(n^{th}\) row of the triangle (the counting of entries in a row starts with 0)
- Probability
- As an example the number of ways a fair coin when tossed \(4\) times will produce exactly two heads
- This follows the binomial expansion \((h + t)^{4}\) where \(h\) represents a head and \(t\) represents a tail. From the triangle, the expansion would be \(h^{4} + 4h^{3}t + 6h^{2}t^{2} + 4ht^{3} + t^{3}\), so the number of ways to get exactly 4 heads is 6 (the second entry in the fourth row)
- This relates to \({4 \choose 2}\)
- The probability of exactly four heads occuring upon the tossing ofa fair coin when tossed \(n\) times
- The probability of this occurring is 6 (the number of successes) divided by \(1 + 4 + 6 + 4 + 1 = 16\) possible outcomes = 6/16 = 0.375
- As an example the number of ways a fair coin when tossed \(4\) times will produce exactly two heads
One interesting thing with respect to Fibonacci sequence is that if one was to consider Pascal’s triangle in perhaps a not so obvious way, there is an astonishing observation to be made. Consider the following diagram where the triangle is redrawn left justified. The numbers along what is called the shallow diagonal are such that their sums follow the Fibonacci Sequence!
