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, ...

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 $\ a,b,c,$  satisfy equality $\ c=a+b,$  then

$\ \gcd(a,b)\ =\ \gcd(a,c)=\gcd(b,c).$

• $\gcd \left(F_{n},F_{n+1}\right)\ =\ \gcd \left(F_{n},F_{n+2}\right)\ =\ 1$

Indeed,

$\gcd \left(F_{0},F_{1}\right)\ =\ \gcd \left(F_{0},F_{2}\right)\ =\ 1$

and the rest is an easy induction.

• $F_{n}\ =\ F_{k+1}\cdot F_{n-k}+F_{k}\cdot F_{n-k-1}$

for all integers $\ k,n,$  such that $\ 0\leq k<n.$

Indeed, the equality holds for $\ 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 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 $\ 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$ . The above constant $\ A$  is known as the famous golden ratio $\ \Phi .$  Thus:

$\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