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

Advertisements

Actions

Information




%d bloggers like this: