Prove that the smallest positive integers for which the Euclidean algorithm takes $n$ steps are $F(n+1)$ and $F(n)$

Question

Problem

The Euclidean state machine is defined by the rule

$$(x,y) \rightarrow (y,\mathrm{rem}(x,y)),$$

for $y > 0$.

Prove that the smallest positive integers $a\geq b$ for which, starting in state $(a,b)$, the state machine will make $n$ transitions are $F(n+1)$ and $F(n)$, where $F(n)$ is the $n$-th Fibonacci number.

Note: $\mathrm{rem}(x,y)$ denotes the remainder of the division of $x$ by $y$.

Can someone please verify this solution?

Solution

Proof by induction.

1. Induction hypothesis: $P(n)$ := the smallest positive integers $a \geq b$ for which, starting in state $(a,b)$, the state machine will make $n$ transitions are $F(n+1)$ and $F(n)$.

2. Base case ($n = 1$):

   $P(1)$ is the proposition: the smallest positive integers $a \geq b$ for which, starting in state $(a,b)$, the state machine will make $1$ transition are $a = F(2) = 1$ and $b = F(1) = 1$.

   $P(1)$ is true, because, starting at state $(F(2), F(1)) = (1,1)$, there's one transition to $(1,0)$, after which there are no more transitions.

3. Inductive step:

   Assume that $P(n)$ is true for some $n \geq 1$. Then, the smallest positive integers $a \geq b$ for which, starting in state $(a,b)$, the state machine will make $n$ transitions are $F(n+1)$ and $F(n)$.

   We want to show $P(n + 1)$.

   Suppose that there are integers $a$ and $b$, with $a \geq b$, for which, starting in state $(a,b)$, the state machine makes $n + 1$ transitions.

   From state $(a,b)$, there is one transition to $(b, \mathrm{rem}(a,b))$. So, from $(b, \mathrm{rem}(a,b))$, the state machine makes $n$ transitions. Therefore, by the induction hypothesis, $b \geq F(n + 1)$ and $\mathrm{rem}(a,b) \geq F(n)$.

   By the division theorem, $\mathrm{rem}(a,b) = a - qb$, where $q$ is an integer. So, $a - qb >= F(n)$. Also, since $a \geq b$, then $q \geq 1$. Therefore:

   $$a \geq F(n) + qb \geq F(n) + b \geq F(n) + F(n + 1) \geq F(n + 2)$$

   Therefore, $a \geq F(n + 2)$ and $b \geq F(n + 1)$.

   Now, I will show that, starting from $(F(n+2), F(n+1))$, the state machine will make $n + 1$ transitions.

   Consider the state $T = (F(n + 2), F(n + 1))$. It has a transition to $T' = (F(n + 1), \mathrm{rem}(F(n+2), F(n+1)))$.

   But $\mathrm{rem}(F(n+2), F(n+1)) = \mathrm{rem}(F(n) + F(n+1), F(n+1)) = \mathrm{rem}(F(n), F(n+1)) = F(n)$.

   So, $T' = (F(n + 1), F(n))$.

   By the induction hypothesis, starting from $T'$, the state machine makes $n$ transitions. Therefore, starting from $T$, the state machine makes $n + 1$ transitions.

   It follows that the smallest positive integers $a \geq b$ for which, starting in state $(a,b)$, the state machine will make $n+1$ transitions are $a=F(n+2)$ and $b=F(n+1)$.

   This proves $P(n + 1)$.

Therefore, by induction, $P(n)$ is true for all $n\geq 1$.