In the euclidian algorithm to find the greatest common denominator $\text{gcd}(n,m)$ of $n$ and $m$ ($m\leq n$) I want to prove the following:
$n_i < \frac{n_{i-2}}{2}\quad \forall i\geq 2$
where $n_i$ is defined as follows:
$n_0:=n$
$n_1:=m$
$n_i := n_{i-2} - \lfloor \frac{n_{i-2}}{n_{i-1}} \rfloor n_{i-1} = n_{i-2} \text{ mod }n_{i-1}\quad \forall i\geq 2$
After reading so many overly-complicated answers in different posts this is what I came to:
$\boxed{(1) \quad a \text{ mod } b < \frac{1}{2}a \quad \forall a,b: 0<b<a \quad}$
Proof:
$a \text{ mod } b <b< \underbrace{\left\lfloor \frac{a}{b} \right\rfloor}_{\geq 1} b \overset{(*)}{=} a - a \text{ mod } b\qquad (*) \text{ } a = \left\lfloor \frac{a}{b} \right\rfloor b + a \text{ mod } b \Rightarrow \left\lfloor \frac{a}{b} \right\rfloor b = a - a \text{ mod } b$
$\Longrightarrow a \text{ mod } b < a - a \text{ mod } b$
$ \Longleftrightarrow a \text{ mod } b < \frac{a}{2} \quad \blacksquare$
Now, specific for the Euclidian algorithm:
$n_i := n_{i-2} \text{ mod }n_{i-1}\quad \forall i\geq 2$
$\Longrightarrow n_i = n_{i-2} \text{ mod }n_{i-1} \overset{(1)}{<} \frac{n_{i-2}}{2} \quad \forall i\geq 2$