Maybe the roughest lesson, someone can ever receive, is this:
$latex 1+1=2$
The implications related to that simple line, can fill a whole library: One of them, is the, so called, Fibonacci sequence:
$latex \{0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...\}$
Defined as:
$latex \displaystyle f_n = \left\{ \begin{array}{lcr} f_0=0;\\ f_1=1;\\ f_n=f_{n-1}+f_{n-2}; \left n \ge 2\\ \end{array}$
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.
$latex \begin{array}{rrc} \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:
$latex \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.
$latex \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.
$latex (a,b)=(r_0,r_1)=(r_2,r_3)=...=(r_{n-1},r_n)=r_n $
$latex \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}
$
if $latex r_{i+1}=0$ then $latex (a,b)=r_i$
Where the function $latex \displaystyle \lfloor x \rfloor$ is the Floor Function, see [3].
Proof:
$latex \displaystyle (f_{n},f_{n-1})=(r_0,r_1)$
$latex \displaystyle r_2=r_0-r_1*\bigg\lfloor\frac{r_0}{r_1}\bigg\rfloor$
$latex \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 $
$latex \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)$
$latex \displaystyle f_{n-2}\le f_{n-1} \implies \bigg\lfloor\frac{f_{n-2}}{f_{n-1}}\bigg\rfloor=0$
$latex \displaystyle r_2=f_n-f_{n-1}=f_{n-2}$
$latex \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
