Prove that if Euclid's algorithm applied to the pair $(u,v)$ takes $n$ steps, then $u \geq f_{n+2}$ and $v \geq f_{n+1}$

Question

Let $u, v \in Z^+$ satisfy $u > v$. Prove that if Euclid's algorithm applied to the pair $(u,v)$ takes $n$ steps, then $u \geq f_{n+2}$ and $v \geq f_{n+1}$. Where the $f_n$ values refer to the Fibonacci sequence.

Answer 1

Denote $E(x,y)$ the number of steps taken for pair $(x,y)$ where $x\geq y$.

First, the algorithm will generate a sequence of equations:
$u=vq_1+r_1$
$v=r_1q_2+r_2$
$r_1=r_2q_3+r_3$
...
where $0\leq r_i<r_{i-1}$ and $q_i\geq1$ for $i=1,2,...,n$

Since $E(u,v)=n$, there are $n$ equations and $r_n=0$. We can rewrite the equations as:
$s_{n+2}=s_{n+1}p_n+s_{n}$
$s_{n+1}=s_{n}p_{n-1}+s_{n-1}$
...
$s_{3}=s_{2}p_{1}+s_{1}$
where $u=s_{n+2}, v=s_{n+1}$ and $r_i=s_{n+1-i},p_i=q_{n+q-i}$ for $i=1,2,...,n$

Now we can prove $s_{n+2}\geq f_{n+2}$ and $s_{n+1}\geq f_{n+1}$ by strong induction on $i$.

First for base, $s_1=0=f_1 \geq f_1$ and $s_2\geq 1=f_2$ for obvious reasion.

Now assume $s_i \geq f_i$ for all $i\leq k$. Now let's look at $i=k+1$.
Since $s_{k+1}=s_kp_{k-1}+s_{k-1} \geq s_k+s_{k-1} \geq f_k+f_{k-1}=f_{k+1}$ we are done fore the $k+1$ case. By induction, we can conclude $s_{n+2}\geq f_{n+2}$ and $s_{n+1} \geq f_{n+1}$.