I am trying to prove a part of the therom stating:
let $a,b\in \Bbb N$ such that $1 \lt b \lt a$ assume euclidean algorithm takes n steps show that $b\ge F_n$ where $F_n$ is the nth fibonacci number.
Based on this https://en.wikipedia.org/wiki/Lam%C3%A9%27s_theorem wiki page here is my attempt:
Applying Euclidean algorithm to calculate the $gcd(a,b)$ provides two sequences $ (r_0,r_1,\dots,r_n), (q_1,q_2,\dots,q_n)$ such that $r_0$=a ,$r_1$=b , $r_{n+1}$=0. We get that for every $1\le i \le n (i\in \Bbb N)$ $q_i ,r_i \in \Bbb N$ : $r_{i-1}=q_ir_i+r_{i+1}$ and a sequance $1 \le r_n \lt r_{n-1} \lt \dots \lt r_1 \lt r_0$. Now we will do induction on the size of n to proof the theorm: When n=1 we get that $F_1$ = 1 and $r_n = r_1 = b$ hence we get $b \ge F_1$ as promised.
Now here is a mistake I know I did the induction step: Let $i \in \Bbb N$ ($1\le i \le n$) such that for any 1<k<i ($k \in \Bbb N$) we get $r_{n-k+1} \ge F_k$ we shall proof for i:
$r_{n-i+1} = q_{n-i+2}r_{n-i+2} + r_{n-i+3} \ge r_{n-i+2} + r_{n-i+3} \ge $(induction assumption)$ F_{i-1} + F_{i-2} = F_i$
We got that $r_{n-i+1} \ge F_i$ hence if we plug i = n we get that $b = r_1 = r_{n-n+1} \ge F_n$ we got that $b \ge F_n$ as promised.
On the wiki page they said an induction is needed for the proof I am having an hard time coming with the right staetment for the induction step I both need n to be arbitry and and index i such that everything after the step works. Any help would be appreciated!