Fibonacci number

In mathematics, the Fibonacci numbers form a sequence in which the first number in the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers. In mathematical terms, it is defined by the following recurrence relation:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n := \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F_{n-1}+F_{n-2} & \mbox{if } n > 1. \\ \end{cases} }

The sequence of Fibonacci numbers starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

The sequence of Fibonacci numbers was first used to represent the growth of a colony of rabbits, starting with a single pair of rabbits.

Properties

We will apply the following simple observation to Fibonacci numbers:

if three integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a,b,c,}   satisfy equality Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c = a+b,}   then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \gcd(a,b)\ =\ \gcd(a,c)=\gcd(b,c).}

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd\left(F_n,F_{n+1}\right)\ =\ \gcd\left(F_n,F_{n+2}\right)\ =\ 1}

Indeed,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd\left(F_0,F_1\right)\ =\ \gcd\left(F_0,F_2\right)\ =\ 1}

and the rest is an easy induction.

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n\ =\ F_{k+1}\cdot F_{n-k} + F_k\cdot F_{n-k-1}}

for all integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k,n,}   such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0\le k < n.}

Indeed, the equality holds for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k=0,}   and the rest is a routine induction on $\ k.$

Next, since $\gcd \left(F_{k},F_{k+1}\right)=1$,  the above equality implies:

$\gcd \left(F_{k},F_{n}\right)\ =\ \gcd \left(F_{k},F_{n-k}\right)$

which, via Euclid algorithm, leads to:

• $\gcd(F_{m},F_{n})\ =\ F_{\gcd(m,n)}$

Let's note the two instant corollaries of the above statement:

• If $\ m$  divides $\ n\$ then $\ F_{m}\$ divides $\ F_{n}\$

• If $\ F_{p}\$  is a prime number different from 3, then $\ p$  is prime. (The converse is false.)

• $\sum _{i=0}^{n}F_{i}^{2}=F_{n}\cdot F_{n+1}$

Direct formula and the golden ratio

We have

$F_{n}\ =\ {\frac {1}{\sqrt {5}}}\cdot \left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)$

for every $\ n=0,1,\dots$ .

Indeed, let  $A:={\frac {1+{\sqrt {5}}}{2}}$  and  $a:={\frac {1-{\sqrt {5}}}{2}}$ .  Let

$f_{n}\ :=\ {\frac {1}{\sqrt {5}}}\cdot (A^{n}-a^{n})$

Then:

• $f_{0}=0\$     and     $\ f_{1}=1$
• $A^{2}=A+1\$     hence     $\ A^{n+2}=A^{n+1}+A^{n}$
• $a^{2}=a+1\$     hence     $a^{n+2}=a^{n+1}+a^{n}\$
• $f_{n+2}\ =\ f_{n+1}+f_{n}$

for every $\ n=0,1,\dots$. Thus $\ f_{n}=F_{n}$  for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=0,1,\dots,} and the formula is proved.

Furthermore, we have:

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\cdot a = -1\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A > 1\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1 < a < 0\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2}\ >\ \left|\frac{1}{\sqrt{5}}\cdot a^n\right|\quad\rightarrow\quad 0}

It follows that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n\ }   is the nearest integer to  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{5}}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n}

for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=0,1,\dots} . The above constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A}   is known as the famous golden ratio Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Phi.}   Thus:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi\ =\ \lim_{n\to\infty}\frac{F(n+1)}{F(n)}\ =\ \frac{1+\sqrt{5}}{2}}

Further reading

• John H. Conway und Richard K. Guy, The Book of Numbers, ISBN 0-387-97993-X