These are the crucial steps (for a modified division algorithm where $q$ is the nearest integer to the $b/a$): $ \forall i:~ r_{i+1} \le \frac{r_i}{2} \quad \implies \quad \forall i:~ r_{i} \le 2^{-i}r_0 \quad \implies \quad r_{n} \le 2^{-n}b<1 $ I'm assuming $r_0=\min(a,b)\le b <2^n$, and that each $r_i$ is the signed residue with smallest magnitude.
For Fibbonacci numbers $b=F_k=\frac{(1+\sqrt5)^k-(1-\sqrt5)^k}{2^k\sqrt5}$ and $a=F_{k-1}$ (representing a worst case analysis), if we start with $b=q_0a+r_0$, then we find $q_i=1~(\forall i)$, $r_0=F_k-F_{k-1}=F_{k-2}$, and by induction, $r_i=F_{k-i}-F_{k-i-1}=F_{k-i-2}$. This shows that the algorithm terminates when $i=k-2$. However, for $k$ large, $\log_2F_k\approx0.694241k-0.16096$ (using the dominating term). This furnishes an example where $b<2^n$ (for $n=\lceil0.694241k-0.16096\rceil$) requires $k-2>n$ steps, still much better than the $2n$ apparently required by the regular division algorithm.
For the regular division algorithm, where each integral quotient $q$ is the greatest integer less than or equal to the rational quotient -- also called the (mathematical) floor function (which is asymmetric, unlike its analogue in most computer language implementations, which is an odd function), and each remainder $r$ is non-negative, say we start and end as follows: $ \eqalign{ a &=q_0\, b +r_0 &\qquad 0< r_0 Now the worst case (slowest) "decay" of $\{r_k\}_{k=0}^m$ is also the best case (fastest) "growth" of $\{r_m,r_{m-1},\dots,r_0\}$. But we also know that it cannot be the case that $r_k=r_{k-1}-1$ for all $m\ge k\ge 0$ (and m>1). This is because as soon as $r_k$ gets so close to $r_{k-1}$ as $r_{k-1}-1$ we are at the "antepenultimate" step, i.e., the next remainder, $r_{k+1}$, will be one, the GCD. A graceful argument will in fact show that, in the worst case, the remainders $r_k$ decay by a factor of the golden ratio, $\phi=\frac{1+\sqrt5}{2}$, here as well, i.e. $r_k < \phi^{-k}r_0$. Since $\phi^2=\frac{3+\sqrt5}{2}>2$, we get the fact you mention in your OP, and an analogous argument to mine above gives us the bound with $2n$.