Proving an inequality involving euclidean algorithm

Question

I am trying to prove that in the euclidean algorithm, for all of the remainders $ r_k $ in the sequence generated by the algorithm that $ r_{k+2} \leq \frac{r_k}{2}$. So this means if we are taking the $gcd(m,n)$ and $min(m,n) \leq 2^k $ then $r_0 = m,r_1 = n $ where $m\geq n$. So $r_2 = r_0 \mod r_1 $ and $r_3 = r_1 \mod r_2 $. Then $r_1,r_2 \leq 2^k $ and $r_3 \leq min(r_1,r_2,r_1-r_2)$ then the only way that $r_3 > 2^{k-1} $ is $(1)\,\,\, min(r_1,r_2) > 2^{k-1} $ and $(2)\,\,\,\,a_1-a_2 > 2^{k-1}$. But here is the problem, someone told me that this directly implies that $ max(a_1,a_2) > 2^k $ and this is a contradiction, so the original statement is proven. Why do inequalities (1) and (2) imply that?

Answer 1

Just note that min$(r_1,r_2)=r_2$. Thus (1) implies $r_2>2^{k-1}$ and (2) implies $r_1>r_2+2^{k-1}$ from which it follows that $r_1>2^k$.