Fibonacci number

In mathematics, the Fibonacci numbers form a sequence defined by the following recurrence relation:

$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 start: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Properties

• The quotient of two consecutive fibonacci numbers converges to the golden ratio: $\lim _{n\to \infty }{\frac {F(n+1)}{F(n)}}=\varphi$
• If $\scriptstyle m>2\$ divides $\scriptstyle n\$ then $\scriptstyle F_{m}\$ divides $\scriptstyle F_{n}\$
• If $\scriptstyle p\geq 5$ and $\scriptstyle F_{p}\$ is a prime number then $p$ is prime. (The converse is false.)
• $\operatorname {gcd} (f_{m},f_{n})=f_{\operatorname {gcd} (m,n)}$
• $F_{0}^{2}+F_{1}^{2}+F_{2}^{2}+...+F_{n}^{2}=\sum _{i=0}^{n}F_{i}^{2}=F_{n}\cdot F_{n+1}$

Direct formula

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 $\ n=0,1,\dots ,$ and the formula is proved.

Furthermore, we have:

• $A\cdot a=-1\$
• $A>1\$
• $-1<a<0\$
• ${\frac {1}{2}}\ >\ \left|{\frac {1}{\sqrt {5}}}\cdot a^{n}\right|\quad \rightarrow \quad 0$

It follows that

$F_{n}\$  is the nearest integer to  ${\frac {1}{\sqrt {5}}}\cdot \left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}$

for every $\ n=0,1,\dots$ . It follows that  $\lim _{n\to \infty }{\frac {F(n+1)}{F(n)}}=A$;  thus the value of the golden ratio is

$\ \varphi \ =\ A\ =\ {\frac {1+{\sqrt {5}}}{2}}$ .

Further reading

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

Applications

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