Derivation of nth term of Fibonacci series using the first two terms

My father was previously a mathematics professor and my brother is involved in computer engineering. Needless to say, I was brought up in an environment filled with mathematics and computers. I too found great interest in these two subjects which encouraged me to explore their depths. Consequently, I had more knowledge than the other students of my class regarding these two subjects.

 

I was in the 6th grade when my brother encouraged me to write a computer program on the Fibonacci series. I had no idea about how to proceed. Later in the evening, I asked my brother to help. With his assistance, I managed to run the program successfully.

 

I rushed to my father to tell him about it.  He had the habit of relating almost everything with mathematics. He at once asked me what I knew about the Fibonacci series with respect to mathematics.

 

I then realized that I have seen Arithmetic series, Geometric series and Harmonic series, but never before a Fibonacci series. I had absolutely no understanding about a Fibonacci series equation. Thus, I decided to try and find out myself.

 

In the process of my study, I came across the term, “golden ratio.” It surprised me to note that the Great Pyramid, hurricanes, cosmos, anatomies, and flower petals, all, maintain the golden ratio. Even the length and width of each DNA turn and Beethoven’s 5th symphony fit the golden ratio; if a musical note maintains the ratio, it becomes soothing to the ear.

 

This field proved to be more interesting than I ever expected and therefore it urged me to fortify my understanding of it. In this IA, I will derive the equation of nth term of a Fibonacci Sequence and represent it graphically for a better, clearer understanding.

The objective of this exploration is to derive a relation between the terms of a Fibonacci Sequence which facilitates  the non-sequential calculation of a Fibonacci Sequence term from an antecedent term or a subsequent term.

What is the generalized scaling factor which should be multiplied with any term of the Fibonacci Sequence to get the next term?

In the Fibonacci Sequence, each term is the sum of previous two terms. Each term in this sequence can be expressed as:

 

T_n = T_{n - 1} + T_{n - 2}  ..............(equation - 1)

 

Example of a Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 …

Let us plot a Fibonacci Sequence where the first two terms are taken as 0 and 1. Now, the graph is plotted taking the abscissa of each point as the present term (T_n) and ordinate of each point as the previous term (T_{n - 1}). The graphs have been plotted using online tool Desmos.

In Fig. 1, we have observed that the points of the sequence lie close to the straight line. However, in Fig. 2, it has been observed that as the value of n increases, the points of the sequence lie exactly (with negligible percentage of error) on the straight line. The equation of the straight line for the above-mentioned Fibonacci Series is given by:

 

y = 0.6181x - 0.0330268 ……………(equation - 2)

 

Since all the values of x and y are not the terms of the Fibonacci Sequence, this equation cannot be taken as the equation of Fibonacci Sequence.

 

If the Fibonacci Sequence is developed representing in a matrix form with the value of present term at position ROW 1 and COLUMN 1, and the value of the previous term at ROW 2 and COLUMN 1 in a [2 × 1] matrix, from the properties of Eigen Vectors, the above straight line (2) can be stated as the Eigen Vector of the Matrix. Using the Eigen Value, we will be able to find the next values of the sequence.

 

Then the matrix will be:

 

\(\biggl({T_n\over T_{n-1}}\biggl)\ =(1\ 1\ 1\ 0)\biggl({T_{n-1}\over T_{n-2}}\biggl)\)……………(equation - 3)

 

\(=> \biggl({x\over y}\biggl)=(1\ 1\ 1\ 0)\biggl({T_{n-1}\over T_{n-2}}\biggl) \).……………(equation - 4)

 

Here, the value of present term is denoted as x, and the value of the previous term is denoted as y.

A sequence is defined by:

 

\(u_1 = 1,u_n = {1\over 1+u_{n-1}}\{for n > 1\}\)

 

The first five terms of this sequence are given as follows:

 

u₁ = 1

 

\(u_2 =  {1\over 1+u_1} \ ={1\over 1+1} = 0.5 \)

 

\(u_3 {1\over 1+u_2} \ ={1\over 1+0.5} = 0.6667\)

 

\(u_4 ={1\over 1+u_3} \ ={1\over 1+0.6667} = 0.6000\)

 

\(u_5 = {1\over 1+u_4} \ ={1\over 1+0.6000} = 0.625\)

 

Value of all the subsequent terms are solved using a python code which is shown. The python code was simulated in PyCharm IDE.

 

From the above result, we can see that, 11^th term (u₁₁) onwards, the value of every term is approximately equal to 0.618.

From the graph and the values of each term as shown in Figure 3 and Figure 4, it can be noted that with increase in the number of terms n, the value of the term tends to become constant.

Eigen Vector of any matrix may be defined as a non-zero vector of a straight line which only gets scaled without any rotation when multiplied by the matrix.

 

The Eigen Vector \(\vec{ v}\) of any Matrix A may be represented as the equation stated below, where \(\lambda\) is the Eigen Value of the Eigen Vector.

 

\(\)

\(A \vec{ v}\ =\ \lambda \vec{ v}\)

 

\(=> A \vec{ v}\ =\ \lambda \vec{ v}\)……………………(equation - 6)

 

Here I is an identity matrix with the order of Matrix A.

Eigen Value  of an Eigen Vector may be defined as the factor by which it is scaled.

 

From Equation (6), let us derive the formula of Eigen Value:

 

\(A\vec v \ = \lambda I \ \vec v\)

 

\( => A\vec v \ = \lambda I \ \vec v = 0\)

 

\( => [A \ - \lambda I] \ \vec v = 0\) ………………………(equation - 7)

 

From the definition of Eigen Vector, \(\vec v\) is a non-zero vector. So, we can write:

 

det det ( A - λI ) = 0 …………………………(equation - 8)

 

This is defined as the Characteristic Polynomial of a matrix.

In this section of the exploration, I will try to derive the equation of Fibonacci Sequence using the above equations (4), (7), and (8) which we have derived from the information discussed above.

 

\(\biggl({T_n\over T_{n-1}}\biggl) = (1\ 1\ 1\ 0)\biggl({T_{n-1}\over T_{n-2}}\biggl)\)

 

For simplicity, let us consider: (1 1 1 0 ) =  X

 

\(∴\biggl({T_n\over T_{n-1}}\biggl)\ = X \biggl({T_{n-1}\over T_{n-2}}\biggl)\)

 

\(=>\bigg(\frac{T_n}{T_{n-1}}\bigg)=X\bigg\{X\bigg(\frac{T_{n-2}}{T_{n-3}}\bigg)\bigg\}=X^2\bigg(\frac{T_{n-2}}{T_{n-3}}\bigg)\)

 

\(=> \biggl({T_n\over T_{n-1}}\biggl)\ = X^{n-1} \bigg({T_{1}\over T_{0}}\bigg) = X^{n-1}\biggl({1\over 0 }\biggl) \)

 

So, we can see that by substituting the values of T for different values of n with the principal equation (4), we can derive a relationship of nth term with the first two terms.

 

In order to diagonalize the value of X rather than X ^n-1, let us consider two non-zero matrices M and K, such that:

 

X.M = M.K

 

=> X = M.K.M ^-1

 

=> K = M ^{- 1}.X.M ……………………(equation - 9)

 

Now, we will find the value of K using the characteristic equation of Eigen Vectors and Eigen Values.

 

From equation (8), we can write:

 

det det  ( A - λI ) = 0

 

Here,  A = X = (1 1 1 0 )  and I = (1 0 0 1)

 

∴ det det {(1 1 1 0 ) - λ (1 0 0 1)} = 0

 

=> det det (1 - λ 1 1 - λ) = 0

 

=> (1 - λ)( - λ) - (1) (1) = 0

 

=> λ² - λ - 1 = 0………………………(equation - 10)

 

Using Sreedhar Acharya’s Formula

 

\(\lambda_1 = {1+\sqrt{5}\over 2}\)

 

\(\lambda_2 = {1-\sqrt{5}\over 2}\)

 

From equation (7), we can write:

 

Case 1: Let, λ = λ₁

 

_{\(\big[X - \lambda_1I\big]\vec v_1\ = 0\)}

 

\(=> (1 - \lambda _1 11- \lambda_1)\biggl({x\over y}\biggl) = 0\)

 

\(=>\biggl({x -x\lambda_1 + y\over x-y\lambda_1}\biggl) = 0\)

 

From the above equation, we can write,

 

x - yλ₁ = 0

 

=> x = yλ₁

 

Let y = 1, then the value of \(x = \lambda_1\)

 

\(\vec v_1= \biggl({\lambda_1\over 1}\biggl)\)

 

Case 2: Let, λ = λ₂

 

_{\(\big[X - \lambda_2I\big]\vec v_2\ = 0\)}

 

\(=> (1 - \lambda _2 \ 1\ 1 - \lambda _2)({x\over y}) = 0\)

 

\(=> \biggl({x-x\lambda _2 + y \over x-y\lambda_2}\biggl)\ = 0\)

 

From the above equation, we can write,

 

x - yλ₂ = 0

 

=> x = yλ₂

 

Let y =1 then the value of \(x = \lambda_2.\)

 

\(\vec v_2 = \bigg({\lambda _2\over 1}\bigg)\)

 

Therefore, we can conclude that:

 

M = (v₁,v₂) = (λ₁ λ₂ 1 1)

 

\(M^{-1}\ = {1\over detdet (\lambda_1 \lambda _2\ 1\ 1)}adj(\lambda_1 \lambda _2\ 1\ 1)\)

 

\(=> M^{-1}\ ={1\over \lambda _1 - \lambda_2}(1 -\lambda_2 -1 \lambda_1)\)

 

\(=> M^{-1}\ = {1\over {1+\sqrt{5}\over 2}{1-\sqrt{5}\over 2}} (1 - \lambda _2 - 1\lambda_1)\)

 

\(=> M^{-1}\ = {1\over \sqrt{5}} (1 - \lambda _2 - 1\lambda_1)\)

 

From equation (9), we can write:

 

K = M^-1.X.M

 

\(=> K ={1\over \sqrt{5}} (1-\lambda_2 - 1\lambda_1) . (1\ 1\ 1\ 0). (\lambda_1\lambda_2\ 1\ 1)\)

 

\(=> K ={1\over \sqrt{5}} (1-\lambda_2 - 1\lambda_1) . (\lambda_1 + 1\lambda_2 + 1\lambda_1\lambda_2)\)

 

\(=> K ={1\over \sqrt{5}} (\lambda_1+1 -\lambda_1\lambda_2 - \lambda^2_2 + \lambda_2 +1\lambda^2_1 -\lambda_2 -1 -\lambda _2 -1 + \lambda_1\lambda_2)\)

 

\(=> K ={1\over \sqrt{5}}\bigg({\lambda_1 + 1 - {1+\sqrt{5}\over 2}}.{1-\sqrt{5}\over 2}0\ 0- \lambda_2 - 1 + {1+\sqrt{5}\over 2}.{1-\sqrt{5}\over 2}\bigg)\)

 

Since, λ² - λ - 1 = 0

 

\(=> K ={1\over \sqrt{5}} (\lambda_1+ 1 + 1\ 0\ 0 - \lambda_2- 1 -1)\)

 

\(=> K ={1\over \sqrt{5}}\biggl({1+\sqrt{5}\over 2}+ 2\ 0\ 0 \ - {1-\sqrt{5}\over 2} -2\biggl)\)

 

\(=> K ={\sqrt{5}\over 5}\biggl({5+\sqrt{5}\over 2}\ 0\ 0 \ {-5 + \sqrt{5}\over 2} \biggl)\)

 

\(=> K =\biggl({5\sqrt{5}+5\over 10}\ 0\ 0 \ {- 5\sqrt{5} + 5\over 10} \biggl)\)

 

\(=> K =\biggl({\sqrt{5}+1\over 2} \ 0\ 0 \ {- \sqrt{5} + 1\over 2} \biggl)\)

 

\(=> K =(\lambda _1\ 0\ 0\ \lambda_2)\)

 

Now, we know that

 

X = M . K . M^-1

 

^{\(=>X^{n-1}\ = ( M.K.M^{-1})^{n-1}\)}

 

=> X^n-1 = M . K . M^-1 M . K . M ^-1 M . K . M ^-1 M . K . M ^-1 …………(upto n^-1 times) M . K . M^-1

 

=> X^{n - 1} = M . K . K . K . K …………(upto n^-1 times) K . M^-1

 

=> X^{n - 1} = M . K^{n - 1}. M ^-1

 

\(∴ K^{n-1} = \biggl(\lambda _1^{n-1}\ 0\ 0 \ \lambda_2^{n-1}\biggl)\)

 

Initially we represented the nth term in terms of first two terms as:

 

\(\biggl({T_n\over T_{n-1}}\biggl)= X^{n-1}\biggl({T_1\over T_0}\biggl) = X^{n-1}\biggl({1\over 0}\biggl)\)

 

\(\biggl({T_n\over T_{n-1}}\biggl)= M.K^{n-1}.M^{-1} \biggl({1\over 0}\biggl)\)

 

\(=> \biggl({T_n\over T_{n-1}}\biggl) \ =(\lambda _1 \lambda_2\ 1\ 1 ).\biggl(\lambda_1^{n-1}\ 0 \ 0 \ \lambda _2^{n-1}\biggl) . {1\over \sqrt{5}}(1 - \lambda_2\ - \ 1\lambda_1)({1\over 0})\)

 

\(=> \biggl({T_n\over T_{n-1}}\biggl) \ = {1\over \sqrt{5}} (\lambda_1 \lambda_2\ 1\ 1).\biggl({\lambda_1^{n-1}\over -\lambda_2^{n-1}}\biggl)\)

 

\(=> \biggl({T_n\over T_{n-1}}\biggl) \ = {1\over \sqrt{5}}\biggl({\lambda_1^{n}- \lambda ^n_2\over -\lambda_1^{n-1}- \lambda_2^{n-1}}\biggl)\)

 

\( ∴ T_n= {1\over \sqrt{5}}(\lambda^n_1\ - \lambda^n_2)\)

 

\(=> T_n = {1\over \sqrt{5}}({1+\sqrt{5}\over 2})^n\ - ({1-\sqrt{5}\over 2})^n\)

 

\(∴ T_{n-1} = {1\over \sqrt{5}} (\lambda^{n-1}_1\ - \lambda_2^{n-1})\)

 

\(=> T_{n-1} = {1\over \sqrt{5}} ({1+\sqrt{5}\over 2})^{n-1} - ({1-\sqrt{5}\over 2})^{n-1}\)

 

Lastly, the limiting ratio of two consecutive terms is given below:

 

\(T_n\over T_{n-1}\)

 

\({1\over \sqrt{5}}(\lambda_1^n - \lambda_2^n)\over {1\over \sqrt{5}}(\lambda_1^{n-1}\ - \lambda_2^{n-1})\)

 

\(\lambda_1^n({1 {\lambda^n_2\over \lambda_1^n}})\over \lambda_1^{n-1}(1 - {\lambda_2^{n-1}\over \lambda_1^{n-1}}))\)

 

\(\lambda_1({1 - {\lambda^n_2\over \lambda_1^n}})\over (1 - {\lambda_2^{n-1}\over \lambda_1^{n-1}}))\)

 

\(({1 - {\lambda^n_2\over \lambda_1^n}})\over (1 - {\lambda_2^{n-1}\over \lambda_1^{n-1}}))\)

 

\(= \lambda _1 = {1+\sqrt{5}\over 2} = 1.61803399 \)

 

\(\lambda_2\over \lambda_1\)

 

\(= {{1-\sqrt{5}\over 2}\over {1+ \sqrt{5}\over 2}}\)

 

\(= {{(1-\sqrt{5}})^2\over (1+ \sqrt{5})(1-\sqrt{5}) }\)

 

\(= {1-2\sqrt{5} + 5 \over 1-5}\)

 

\(= { 6-2\sqrt{5}\over -4}\)

 

\(= - { 3- \sqrt{5}\over 2}\)

 

≈ - 0.3819

 

\(- 1< {\lambda_2\over \lambda_1}<0\)

 

\(=> 0 < \biggl|{\lambda_2\over \lambda_1}\biggl|<1\)

 

\(=> ({\lambda_2\over \lambda_1})^n \ = 0\)

 

Thus, we can state that the ratio between any two term of a Fibonacci Sequence is 1.618. It should be noted that the ratio is constant for any two term of the Fibonacci Sequence because the Fibonacci function has been expressed as an Eigen Vector and  is the Eigen Value of the vector. Eigen Value is the constant value for all the terms of the function. However, it has been verified in the next section.

 

Furthermore, this value is also equal to the golden ratio of the Fibonacci Spiral.

 

Moreover, this is the value of Eigen Value . Thus, it also verifies that v is the Eigen Vector of Matrix X. Furthermore, the straight line (2) is actually the Eigen Vector because all the points that lie on the Eigen Vector are actually the terms of the sequence and the next term can be found by simply multiplying the present term with the Eigen Value.

Case 1 We will find the next terms using the Golden Ratio 1.61803399. Let us assume u₃ = 1.

Sample Calculation

 

Observed Value of 5^th Term = (Value of 4^th Term) × 1.618

 

= 2 × 1.618 = 3.236  ≈ 3

 

Error of 5^th Term = 3.2360 - 3 = 0.2360

The above graph shows the variation between absolute error in determining the value of any term of the Fibonacci sequence using Golden ratio with respect to the number of terms. It is observed from the graph that the absolute error decreases exponentially with respect to the number of terms. The value of absolute error decreases from 0.382 to 0.003 when the number of terms is increased from 2 to 12 at a regular interval of 1 term. The equation of trend obtained in the graph using MS Excel is shown below:

 

y = 1.005 × e^-0.483x

 

In the above-mentioned equation, y represents the absolute error of any term and x denotes the number of terms. Analyzing the above equation, it can be said that:

 

0 = 1.005 × e^-0.483x

 

=> e^-0.483x = 0

 

Taking logarithm in both sides of the equation:

 

ln ln e^-0.483x = ln ln 0

 

=> - 0.483x × ln ln e = - ∞

 

=> x = ∞

 

Hence, it can be said that the absolute error in determining the value of the term will be equal to zero for nth term where n = ∞.

 

Lastly, there are no significant outliers in the graph which strengthen the analysis and the equal of trend. It is again justified by the maximum value of Regression coefficient.

So, let as assume that, if n tends to infinity, the value of u_n will tend to become constant (u).

 

Mathematically, it can written as:

 

\(u_n = \frac{1}{1+u_{n-1}}\{for n >1\}\)

 

=> u_n + u_n u_{n - 1} = 1

 

Taking limits in both sides:

 

u_n + u_n u_{n - 1} = 1

 

=> u_n + u_n u_{n - 1} = 1

 

=> u_n + u_n u_{n - 1} = 1

 

=> u + u.u = 1

 

=> u² + u - 1 = 0

 

Solving the above equation using Sreedhar Acharya’s Formula, we get:

 

\(u=\frac{-1±\sqrt{1+4}}{2}\)

 

\(=>u=\frac{-1±\sqrt{5}}{2}\)

 

From the above study of the sequence, we can conclude that, there cannot be any negative value of terms of the sequence as n >1. Therefore, we can write,

 

\(u=\frac{-1+\sqrt5}{2}\)

 

=> u = 0.618

Case 2: We will find the previous terms using the Golden Ratio, 0. 61803399. Let us assume u₁₄ = 233.