# Fibonacci number

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

This editable Main Article is under development and subject to a disclaimer.

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

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

It was first used to represent the growth of a colony of rabbits, starting with a single pair of rabbits. It has applications in mathematics as well as other sciences, and is a popular illustration of recursive programming in computer science.

## Divisibility properties

We will apply the following simple observation to Fibonacci numbers:

if three integers ${\displaystyle \ a,b,c,}$  satisfy equality ${\displaystyle \ c=a+b,}$  then

${\displaystyle \ \gcd(a,b)\ =\ \gcd(a,c)=\gcd(b,c).}$

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

Indeed,

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

and the rest is an easy induction.

• ${\displaystyle F_{n}\ =\ F_{k+1}\cdot F_{n-k}+F_{k}\cdot F_{n-k-1}}$
for all integers ${\displaystyle \ k,n,}$  such that ${\displaystyle \ 0\leq k

Indeed, the equality holds for ${\displaystyle \ k=0,}$  and the rest is a routine induction on ${\displaystyle \ k.}$

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

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

which, via Euclid algorithm, leads to:

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

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

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

## Algebraic identities

• ${\displaystyle F_{n-1}\cdot F_{n+1}-F_{n}\,^{2}\ =\ (-1)^{n}\ }$     for n=1,2,...
• ${\displaystyle \sum _{i=0}^{n}F_{i}\,^{2}\ =\ F_{n}\cdot F_{n+1}}$

## Direct formula and the golden ratio

We have

${\displaystyle 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 ${\displaystyle \ n=0,1,\dots }$ .

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

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

Then:

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

for every ${\displaystyle \ n=0,1,\dots }$. Thus ${\displaystyle \ f_{n}=F_{n}}$  for every ${\displaystyle \ n=0,1,\dots ,}$ and the formula is proved.

Furthermore, we have:

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

It follows that

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

for every ${\displaystyle \ n=0,1,\dots }$ . The above constant ${\displaystyle \ A}$  is known as the famous golden ratio ${\displaystyle \ \Phi .}$  Thus:

${\displaystyle \Phi \ =\ \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}\ =\ {\frac {1+{\sqrt {5}}}{2}}}$

## Fibonacci generating function

The Fibonacci generating function is defined as the sum of the following power series:

${\displaystyle g(x)\ :=\ \sum _{n=0}^{\infty }F_{n}\cdot x^{n}}$

The series is convergent for  ${\displaystyle \ |x|<{\frac {1}{\Phi }}.}$  Obviously:

${\displaystyle g(x)\ =\ x+x\cdot g(x)+x^{2}\cdot g(x)\ }$

hence:

${\displaystyle g(x)\ =\ {\frac {x}{1-x-x^{2}}}}$

Value ${\displaystyle \ g(x)}$  is a rational number whenever x is rational. For instance, for x = ½:

${\displaystyle {\frac {F_{1}}{2}}+{\frac {F_{2}}{4}}+{\frac {F_{3}}{8}}+\cdots \ =\ 2}$

and for x = −½ (after multiplying the equality by −1):

${\displaystyle {\frac {F_{1}}{2}}-{\frac {F_{2}}{4}}+{\frac {F_{3}}{8}}-\cdots \ =\ {\frac {2}{5}}}$