According to Euclides' algorithm, suppose that $a \ge b \gt 0$, we have
$$ a = bq_0 + r_0 \qquad 0 \lt r_0 \lt b$$ $$ b = r_0q_1 + r_1 \qquad 0 \lt r_1 \lt r_0$$ $$ r_0 = r_1q_2 + r_2 \qquad 0 \lt r_2 \lt r_1$$ $$.$$ $$.$$ $$r_{i-2} = r_{i-1}q_i + r_i \qquad 0 \lt r_i \lt r_{i-1}$$ $$r_{i-1} = r_iq_{i+1} + r_{i+1} \qquad r_{i+1} = 0$$
prove that $b \gt 2^{i/2}$
I haven't been able to prove this even though it seems quite logical.
I need a hint please.
We have: $$r_k=r_{k+1}q_{k+2}+r_{k+2} \geqslant r_{k+1}+r_{k+2}$$ since $r_j>r_{j+1} \implies q_j \geqslant 1$. We then have: $$b \geqslant r_0+r_1 \geqslant 2r_1+r_2 \geqslant 3r_2+2r_3 \geqslant \ldots \geqslant F_{i+2}r_i+F_{i+3}r_{i+1} \geqslant F_{i+2}(1)+0 = F_{i+2}$$ where $F_n$ is the $n^{th}$ Fibonacci number. Now, we only need to show that $F_{i+2} > 2^{i/2}$ for $i \in \mathbb{N}_0$. We can see that this trivially holds true for $i=0,1$. Now, let this hold true for $i=k,k+1$. Then- $$F_{k+2}=F_{k+1}+F_k \geqslant 2F_k > 2 \cdot 2^{{(k-2)}/{2}}=2^{k/2}$$ Thus, by induction hypothesis, we are done. Note that the quotient between consecutive Fibonacci Numbers approaches $\phi=1.618...$ but the ratio required to solve this problem is only $\sqrt{2}=1.414...$ which means that our result can be made much stronger.
