Let us define the height of an integer $a\geq 2$ to be the greatest $n$ such that Euclid's algorithm requires $n$ steps to compute $\gcd(a,b)$ for some positive $b<a$.
[...]
Show that $h(f_{n+2})=n$ and $f_{n+2}$ is the smallest integer of this height (where $f_{n+2}$ is the $n+2$th Fibonacci number) (Elementary Number Theory, Jones & Jones, exercise 1.20)
In previous parts we show that:
- $0\leq f_n < f_{n+1} \qquad \forall n\geq 2$
- For $a>b>0$, if Euclid's algorithm finds $\gcd(a,b)$ in $n$ steps, $a\geq f_{n+2}$ and $b\geq f_{n+1}$.
Proving $h(f_{n+2})=n$
Due to previous result (1), the Fibonacci sequence is increasing for all $n$.
Similarly to previous result (2), in $n+k$ steps we have:
$$\gcd(a,b)\ \text{computed in}\ n+k\ \text{steps} \implies a\geq f_{n+2+k}\ \text{and}\ b\geq f_{n+1+k}\qquad \forall k\geq 1$$
The contrapositive is: $$\gcd(a,b)\ \text{not computed in}\ n+k\ \text{steps} \impliedby a< f_{n+2+k}\ \text{and}\ b< f_{n+1+k}\qquad \forall k\geq 1$$
In the case of $h(f_{n+2})$, $a=f_{n+2}$ and $b<f_{n+2}$ so $a< f_{n+2+k}$ as Fibonacci is an increasing sequence, and $b< f_{n+1+k}$ for a similar reason. Via the contrapositive, this means that $\gcd(f_{n+2},b)$ cannot be computed in $n+k$ steps for all $k\geq 1$, which is equivalent to $h(f_{n+2})$ cannot be computed in $n+1$ steps or more.
The $\gcd(f_{n+2},f_{n+1})$ is computed in $n$ steps so $h(f_{n+2})\geq n$. Due to the previous paragraph, $h(f_{n+2})<n+1$ so $h(f_{n+2})=n$ for all $n \geq 1$. $\blacksquare$
Proving $f_{n+2}$ is the smallest integer with height $n$
Consider $h(f_k)=k-2$ where $k \in [3,n+2)$ using the previous result, and consider further the greatest value of $h(f_k)$ in the interval of $k$.
\begin{align*} \max_{k \in [3,n+2)}h(f_k) &= (n+1)-2 \cr &= n-1 \cr &< n \end{align*}
Therefore $\forall k\in [1,n+2)\ h(f_k)<n$ so $a=f_{n+2}$ is the smallest integer such that $h(a)=n$ for all $n\geq 1$. $\blacksquare$
I would like to know whether these two proofs are correct and well-written and how I can improve on them.