Mridul Gupta

The Fibonacci numbers are the numbers $0,1,1,2,3,5,\dotsc$ In this post, I will label these numbers as $F_0, F_1, F_2, \dotsc$ for convenience. The defining property of the Fibonacci numbers is that $F_n=F_{n-1}+F_{n-2}$ starting with $F_0=0$ and $F_1=1$.

The equation $x^2-x-1=0$ holds a special relationship with the Fibonacci numbers. This relationship is not immediately apparent, and we will have to deform and reshape the equation and its contents a bit to make the relationship visible. First note that the equation can be re-written as $x^2=x+1$. Next let $a,b,c\in\mathbf{R}$ in the following. \[c=ax+b\] Next, we need to morph this equation a bit by multiplying this equation by $x$ on both the sides. $$ \begin{aligned} cx&=x(ax+b)\\ &=ax^2+bx\\ &=a(x+1)+bx=(a+b)x+a \end{aligned} $$ where we have used the fact that $x^2=x+1$. Now this is true in general, but something beautiful happens when we let $a=F_{n-1}$ and $b=F_{n-2}$. I will also use $c_{n-1}$ and $c_n$ in a few places, the reason for which will become apparent from the use. $$ \begin{aligned} c_{n-1}&=F_{n-1}x+F_{n-2}\\ c_n=c_{n-1}x&=F_{n-1}x^2+F_{n-2}x\\ &=F_{n-1}(x+1)+F_{n-2}x\\ &=(F_{n-1}+F_{n-2})x+F_{n-1}\\ &=F_nx+F_{n-1} \end{aligned} $$ The right hand side of the equation is in the form that we need, but we need to work on the left hand side a bit. We now get a sequence of terms $c_n$ when we plug in different natural numbers for $n$. We need an explicit form for the $c_n$, the $n$-th sum of the form $F_nx+F_{n-1}$. Notice that when $n-1=1$ and $n-2=0$, we have $c_1=F_1x+F_0=x$. Further, the next term in the sequence is generated by multiplying with $x$. Therefore, \[c_n=c_{n-1}x=c_{n-2}x^2=\dotsm=c_1x^{n-1}=x^n\] This finally gives us the important equation \[x^n=F_nx+F_{n-1}\] The equation is satisfied by any $x$ that satisfies $x^2-x-1=0$. We have two roots of this equation, let's call them $\varphi$ and $\phi$. Therefore, we get two equations $$ \begin{aligned} \varphi^n&=F_n\varphi+F_{n-1}\\ \phi^n&=F_n\phi+F_{n-1}\\ \end{aligned} $$ By subtracting the two equations we get $$ \begin{aligned} \varphi^n-\phi^n&=F_n(\varphi-\phi)\\ \implies F_n&=\frac{\varphi^n-\phi^n}{\varphi-\phi} \end{aligned} $$ Traditionally, $\varphi$ is the larger root and is called the Golden Ratio.

But that is not the end of it. This kind of derivation can be used to find such closed form solutions for any sequence of the form $F_n=F_{n-1}+F_{n-2}$ regardless of the starting point $F_0$ and $F_1$. For example, let $G_0=2$ and $G_1=4$ and $G_n=G_{n-1}+G_{n-2}$ (I am using $G$ to separate this sequence from the Fibonacci sequence). The following shows the work $$ \begin{aligned} c_1&=G_1x+G_0=4x+2\\ c_2=c_1x&=G_2x+G_1\\ &\quad\vdots\\ c_n=c_1x^{n-1}&=G_nx+G_{n-1}\\ \end{aligned} $$ Putting the value of $c_1$ in the last statement will give us $(4x+2)x^{n-1}=G_nx+G_{n-1}$. Now we can again put in the two solutions and subtract the equations to obtain the solution. $$ \begin{aligned} &(4\varphi+2)\varphi^{n-1}=G_n\varphi+G_{n-1}\\ -&(4\phi+2)\phi^{n-1}=G_n\phi+G_{n-1}\\ \hline &(4\varphi+2)\varphi^{n-1}-(4\phi+2)\phi^n=G_n(\varphi-\phi) \end{aligned} $$ Which gives \[G_n=\frac{(4\varphi+2)\varphi^{n-1}-(4\phi+2)\phi^{n-1}}{\varphi-\phi}\] This can further be simplified $$ \begin{aligned} G_n&=\frac{(4\varphi+2)\varphi^{n-1}-(4\phi+2)\phi^{n-1}}{\varphi-\phi}\\ &=\frac{4\varphi^n+2\varphi^{n-1}-4\phi^n-2\phi^{n-1}}{\varphi-\phi}\\ &=\frac{4\varphi^n-4\phi^n}{\varphi-\phi}+\frac{2\varphi^{n-1}-2\phi^{n-1}}{\varphi-\phi}\\ &=4F_n+2F_{n-1} \end{aligned} $$ With some more work, can this method also be generalised to the situation when we have a sequence of the form $G_n=aG_{n-1}+bG_{n-2}$? You should try it with some arbitrary values of $a,b,G_0,$ and $G_1$.

I want to show one final thing before ending this short post. I want to find the limiting value of the ratio $\frac{F_n}{F_{n-1}}$. We will need to use $r=\phi/\varphi$ to derive this, and we will need to use the fact that $|r|<1$.

$$ \begin{aligned} \lim_{n\to\infty}\frac{F_n}{F_{n-1}}&=\lim_{n\to\infty}\frac{\varphi^n-\phi^n}{\varphi^{n-1}-\phi^{n-1}}\\ &=\lim_{n\to\infty}\frac{\varphi^n}{\varphi^{n-1}}\cdot\frac{1-r^n}{1-r^{n-1}}\\ &=\lim_{n\to\infty}\varphi\cdot\frac{1-r^n}{1-r^{n-1}}\\ &=\varphi \end{aligned} $$

Concrete values of $\varphi$ and $\phi$ are $1.61803398874\dotsc$ and $-0.61803398874\dotsc$ respectively. This gives $r\approx-0.381966$, and $r^{21}=\mathcal{O}(10^{-10})$. Therefore, at around the $21$-st Fibonacci number, this ratio is almost exact, and we can just multiply the number with $\varphi$ and round the number to get the next Fibonacci number. $F_{21}=10946$ while $\varphi F_{21}=17711.00004\approx 17711=F_{22}$.

One can keep talking about the interesting relationships between these numbers but these relationships are numerous, and we must stop at some point. I find this as an adequate stopping point. Until next time.

Edit: After posting this blog, I came across this on wikipedia. Apparently, this formula is called Binet's formula, and there is a much simpler and more elegant proof of this. It follows from observing that $x^n=x^2x^{n-2}=(x+1)x^{n-2}=x^{n-1}+x^{n-2}$. Notice that the powers follow the Fibonacci recurrence relation. This means that $$ \begin{aligned} \varphi^n&=\varphi^{n-1}+\varphi^{n-2}\\ \phi^n&=\phi^{n-1}+\phi^{n-2} \end{aligned} $$ And for any $U_n=a\varphi^n+b\phi^n$, we will have the same recurrence relation because $$ \begin{aligned} U_n&=a\varphi^n+b\phi^n\\ &=a(\varphi^{n-1}+\varphi^{n-2})+b(\phi^{n-1}+\phi^{n-2})\\ &=(a\varphi^{n-1}+b\phi^{n-1})+(a\varphi^{n-2}+b\phi^{n-2})\\ &=U_{n-1}+U_{n-2} \end{aligned} $$ Then we just need to have $a$ and $b$ such that $U_0=0$ and $U_1=1$. This can easily be solved using linear equations, and we get the same results.

Another interesting thing I noted from wikipedia was that since $|\phi|<1$, $\phi^n$ quickly approaches $0$, and thus \[F_n\approx\frac{\varphi^n}{\sqrt{5}}\] where we used the fact that $\varphi-\phi=\sqrt{5}$. In fact $F_n$ is the nearest integer to $\varphi^n/\sqrt{5}$.