## EUCLINACCI – [1]

1 02 2009

Maybe the roughest lesson, someone can ever receive, is this:

$1+1=2$

The implications related to that simple line, can fill a whole library: One of them, is the, so called, Fibonacci sequence:

$\{0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...\}$

Defined as:

$\displaystyle f_{n} = \left\{ \begin{array}{lcr} f_{0}=0;\\ f_{1}=1;\\ f_{n}=f_{n-1}+f_{n-2}; n \ge 2 \end{array} \right\}$

Tabulating the ratio between two consecutive terms of the sequence, appear on insight, two properties:

1) This ratio has a finite limit.
2) Two consecutive Fibonacci numbers are
relatively prime.

$\displaystyle \begin{array}{|r|r|c|} \hline {n} & f_n & f_n/f_{n-1} \\ \hline 0 & 0 & -\\ 1 & 1 & -\\ 2 & 1 & 1.0000 \\ 3 & 2 & 2.0000 \\ 4 & 3 & 1.5000 \\ 5 & 5 & 1.6667 \\ 6 & 8 & 1.6000 \\ 7 & 13 & 1.6250 \\ 8 & 21 & 1.6154 \\ 9 & 34 & 1.6190 \\ 10 & 55 & 1.6176 \\ 11 & 89 & 1.6182 \\ 12 & 144 & 1.6180 \\ 13 & 233 & 1.6181 \\ 14 & 377 & 1.6180 \\ 15 & 610 & 1.6180 \\ 16 & 987 & 1.6180 \\ \hline \end{array}$

To prove the first property, we have:
$\displaystyle I = \lim_{x \to +\infty} \frac{f_n}{f_{n-1}} = \lim_{x \to +\infty} \frac{f_{n-1}+f_{n-2}}{f_{n-1}} = \\ 1 + \lim_{x \to +\infty} \frac{f_{n-2}}{f_{n-1}} = 1 + \lim_{x \to +\infty} \frac{f_{n-1}}{f_n};\\ I=1+\frac{1}{I} \Rightarrow I=1+\frac{1}{I}$

With positive solution, equal to the golden ratio.

$\displaystyle I=\frac{1+\sqrt{5}}{2}=\Phi$

The proof, of this second property, used to be by induction or contradiction [2], but this can also be proved using the oldest procedure designed to calculate de greatest common divisor, GCD, of two integers, known as The Euclidean Algorithm
The Euclidean method constructs a decreasing sequence of integers who share the same GCD.

$(a,b)=(r_0,r_1)=(r_2,r_3)=...=(r_{n-1},r_n)=r_n$

$\left\{\begin{array}{l} a=r_0; \\ b=r_1; \\ r_{i+1}=r_{i-1}-r_i*\bigg \lfloor\frac{r_{i-1}}{r_i}\bigg\rfloor;\\ \end{array}\right\}$

if $r_{i+1}=0$ then $(a,b)=r_i$

Where the function $\displaystyle \lfloor x \rfloor$ is the Floor Function, see [3].

Proof:

$\displaystyle (f_{n},f_{n-1})=(r_0,r_1)$

$\displaystyle r_2=r_0-r_1*\bigg\lfloor\frac{r_0}{r_1}\bigg\rfloor$

$\displaystyle r_2=f_n-f_{n-1}*\bigg\lfloor\frac{f_n}{f_{n-1}}\bigg\rfloor=f_n-f_{n-1}*\bigg\lfloor\frac{f_{n-1}+f_{n-2}}{f_{n-1}} \bigg\rfloor$

$\displaystyle r_2=f_n-f_{n-1}*\bigg\lfloor 1+\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor =f_n-f_{n-1}*\bigg(1+\bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor\bigg)$

$\displaystyle f_{n-2}\le f_{n-1} \implies \bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor=0$

$\displaystyle r_2=f_n-f_{n-1}=f_{n-2}$

$\displaystyle(f_{n},f_{n-1})=(r_0,r_1)=(r_1,r_2)=(f_{n-1},f_{n-2})=...=(2,1)=1$

The Euclidean Algorithm reproduces all FibonacciÂ´s sequence and proves that two consecutive terms are relatively prime.

References:

[1]-Fundamentals of Number Theory William J. LeVeque – Courier Dover Publications, 1996 – ISBN 0486689069, 9780486689067
[2]-Consecutive Fibonacci Numbers Relatively Prime – The Math Forum@Drexel
[3] Weisstein, Eric W. “Floor Function.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/FloorFunction.html