3
$\begingroup$

I have read in a page that " To find the nth term of the Fibonacci series, we can use Binet's Formula"

F(n) = round( (Phi ^ n) / √5 ) provided n ≥ 0
where Phi=1·61803 39887 49894 84820 45868 34365 63811 77203 09179 80576 ... .

my question is,

  • What is this Phi?
  • How they generated this Phi?
$\endgroup$
4
$\begingroup$

$\phi = \frac{1+\sqrt{5}}{2}$ is a very important constant in nature called the golden ratio, it appears in many different guises.

Binets formula is:

$F_n = \frac{(\phi^n - (-\phi)^{-n})}{\sqrt{5}} = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}$

There are many different ways to prove Binet's formula. One I like in particular (which generalises to other linear difference equations) is to use eigenvalues and eigenvectors of a particular matrix. This is essentially the reason behind the appearance of $\phi$.

See here:

http://en.wikipedia.org/wiki/Fibonacci_number

$\endgroup$
3
$\begingroup$

There are different ways of generating $\phi=\frac{1+\sqrt{5}}{2}= 1.618$, and one of them is presented in Professor Strang's book Introduction to Linear Algebra. I'm modifying a bit the details, but the idea is what counts:

In the Fibonacci series, the recursive formula is such that it can be expressed as:

$$\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}=\color{orange}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}$$

Starting at $u_0=\begin{bmatrix}F_1\\F_0\end{bmatrix}=\color{brown}{\begin{bmatrix}1\\0\end{bmatrix}}$, we can proceed as

$$\begin{bmatrix}F_2\\F_1\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^1\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}2\\1\end{bmatrix}$$

and matrix multiply $100$ times to get $F_{100}$:

$$\begin{bmatrix}F_{101}\\\color{blue}{F_{100}}\end{bmatrix}=\color{orange}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{\color{blue}{100}}\color{brown}{\begin{bmatrix}1\\0\end{bmatrix}}$$

which is straightforward if we can eigendecompose the matrix $\color{orange}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}$:

$$\color{orange}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}=S\Lambda S^{-1}=\begin{bmatrix}\vert&\vert\\\text{ev}_1&\text{ev}_2\\\vert&\vert\end{bmatrix}\begin{bmatrix}\lambda_1&0\\0&\lambda_2\end{bmatrix}\begin{bmatrix}\vert&\vert\\\text{ev}_1&\text{ev}_2\\\vert&\vert\end{bmatrix}^{-1}$$

In which case:

$$\begin{bmatrix}F_{101}\\\color{blue}{F_{100}}\end{bmatrix}=\begin{bmatrix}\vert&\vert\\\text{ev}_1&\text{ev}_2\\\vert&\vert\end{bmatrix}\begin{bmatrix}\lambda_1&0\\0&\lambda_2\end{bmatrix}^{\color{blue}{100}}\begin{bmatrix}\vert&\vert\\\text{ev}_1&\text{ev}_2\\\vert&\vert\end{bmatrix}^{-1}\color{brown}{\begin{bmatrix}1\\0\end{bmatrix}}\tag 1$$

So we have to find the eigenvalues of $\begin{bmatrix}1&1\\1&0\end{bmatrix}$:

$$0=\begin{bmatrix}1&1\\1&0\end{bmatrix}-\lambda\begin{bmatrix}1&0\\0&1\end{bmatrix}=\begin{bmatrix}1-\lambda&1\\1&-\lambda\end{bmatrix}$$

Solving for the eigenvalues results in $\large\color{red}{\lambda_1=\frac{1+\sqrt{5}}{2}}$ and $\large\lambda_2=\frac{1-\sqrt{5}}{2}.$

So we have "generated" the golden ratio as the first eigenvalue of the matrix expressing the transformation from each column vector containing two adjacent Fibonacci numbers to to the next overlapping ordered pair.

Here is the plot in relation to the basis vectors in the transformation $\small\begin{bmatrix}\color{orange}{1}&\color{red}{1}\\\color{orange}{1}&\color{red}{0}\end{bmatrix}:$

enter image description here

Just to wrap up the story, the eigenvectors are:

$\text{ev}_1=\begin{bmatrix}\lambda_1\\1\end{bmatrix}$ and $\text{ev}_2=\begin{bmatrix}\lambda_2\\1\end{bmatrix}$

and going back to Eq.1:

$$\begin{bmatrix}F_{101}\\\color{blue}{F_{100}}\end{bmatrix}=\frac{1}{\lambda_1-\lambda_2}\begin{bmatrix}\lambda_1&\lambda_2\\1&1\end{bmatrix}\begin{bmatrix}\lambda_1^{100}&0\\0&\lambda_2^{100}\end{bmatrix}\begin{bmatrix}1&-1\\-\lambda_2&\lambda_1\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}$$

and since $\lambda_2^{100}\simeq 0,$

$$\begin{bmatrix}F_{101}\\\color{blue}{F_{100}}\end{bmatrix}\simeq\frac{1}{\lambda_1-\lambda_2}\begin{bmatrix}\lambda_1&\lambda_2\\1&1\end{bmatrix}\begin{bmatrix}\lambda_1^{100}\\0\end{bmatrix}=\frac{1}{\lambda_1-\lambda_2}\begin{bmatrix}\lambda_1^{101}\\\lambda_1^{100}\end{bmatrix}$$

and

$$F_{100}\simeq\frac{\lambda_1^{100}}{\lambda_1-\lambda_2}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{100}$$

which is the approximation in the OP:

$$\color{blue}{F_n\simeq \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}}$$

$\endgroup$
2
$\begingroup$

The $\varphi$ here is the famous Golden ratio. It appears to be one of those fundamental numbers that arises from the nature itself. The Wikipedia link above provides a good discussion about its nature and its occurences in math.

As for its particular connection to the Fibonacci numbers, Wikipedia again gives a good explanation. (From a philosophical perspective, I would actually say that Fibonacci numbers are more fundamental than $\varphi$, but this is just a personal feeling...)

$\endgroup$
0
$\begingroup$

Maybe you can take a look at this : http://en.wikipedia.org/wiki/Golden_ratio. It is explain how you can calculate the $n^{th}$ term and give a method to calculate $\phi$.

$\endgroup$
0
$\begingroup$

Using generating functions:

\begin{align} \color{brown}{f(x) = \sum_0^\infty F_n x^n} &= F_0x^0 + F_1x^1+F_2 x^2 + F_3 x^3+ F_4 x^4+\cdots\\ xf(x) &= \quad\quad\quad\, F_0x^1+F_1x^2+F_2x^3+F_3x^4+\cdots\\ x^2f(x)&=\quad\quad\quad\quad\quad\quad\,\,F_0x^2+F_1x^3 + F_2x^4+\cdots \end{align}

Since the value of $F_0=0$ and $F_1=F_2=1$, while the recursive formula is $F_{n+2}=F_{n+1}+F_{n}$,

\begin{align} f(x) &= F_1x^1+F_2 x^2 + F_3 x^3+ F_4 x^4+\cdots\\ -\big[ xf(x) &= \quad\quad\quad\, F_1x^2+F_2x^3+F_3x^4+\cdots\big]\\ -\big[x^2f(x)&=\quad\quad\quad\quad\quad\quad\,\,F_1x^3 + F_2x^4+\cdots\big]\\ \quad\\ &\hline\\ (1-x-x^2)f(x)&=x\\ f(x)&=\frac{x}{1-x-x^2} \end{align}

The denominator is a quadratic with roots $0=1-x-x^2$; $\large x=\frac{1\pm\sqrt{5}}{-2}$, or $-\phi$ and $-\psi:$

$$\color{red}{\varphi=\frac{1+\sqrt{5}}{2}} \text{ and } \psi=\frac{1-\sqrt{5}}{2}$$

Hence,

\begin{align} (1-x-x^2)f(x)&=x\\ f(x)&=\frac{x}{1-x-x^2}\\ f(x)&=\frac{-x}{(x+\varphi)(x-\psi)}\\ f(x)&=\frac{A}{x+\varphi}+\frac{B}{x-\psi}\tag 1 \end{align}

Therefore,

$$-x=A(x-\psi)+B(x+\varphi)$$

If $x=-\varphi$, $A=-\frac{\varphi}{\sqrt{5}}$, and if $x=-\psi$, $B=\frac{\psi}{\sqrt{5}}.$ Going back to Eq. 1:

$$f(x)=\frac{1}{\sqrt{5}}\left(\color{blue}{\frac{\psi}{x+\psi}}-\color{red}{\frac{\varphi}{x+\varphi}}\right)\tag 2$$

Since $\varphi=-\frac{1}{\psi}$,

$$\color{blue}{\frac{\psi}{x+\psi}}= \frac{1}{1+\frac{x}{\psi}} =\frac{1}{1-\varphi x} =\sum_{n=0}^\infty \varphi^n x^n\tag{*} $$

(*) using the formula for the geometric series, $\sum_0^\infty x^n= \frac{1}{1-x}.$ In the case of

$$\color{red}{\frac{\varphi}{x+\varphi}}=\sum_{n=0}^\infty \psi^n x^n$$

Going back to Eq.2,

$$f(x)=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^\infty \varphi^n x^n-\sum_{n=0}^\infty \psi^n x^n\right)=\sum_0^\infty \frac{1}{\sqrt{5}}\left( \varphi^n - \psi^n \right)x^n=\color{brown}{\sum_0^\infty F_n x^n}$$

So we get Binet's formula:

$$\large F_n=\frac{1}{\sqrt{5}}(\varphi^n-\psi^n)\tag{Binet's formula}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.