Lemma 6.2. in Scaling Algorithms for the Shortest Path Problem

Question

I have a question regarding the proof of Lemma 6.2. in this paper: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/scaling%20algorithm%20for%20the%20shortest.pdf. The simplified statement is that if we start with an integer $k$, substract $\sqrt{k}$, then substract $\sqrt{k - \sqrt{k}}$ and so on, then $O(\sqrt{k})$ iterations reduce $k$ by at least a factor of 2. How would one prove this? So far I have written down the explicit recursion formula $x_1 := k$, $x_{i+1} = x_i - \sqrt{x_i}$ but don't really see a way to proceed with this. I would appreciate any hints or ideas.

Answer 1

Until the size has been decreased by a factor of $2$, the size is always at least $k/2$, meaning the amount decreased in each step is at least $\sqrt{k/2}$. Since we are decreasing by at least $\sqrt{k/2}$ each time, the number of decreases required to get a total decrease of $k/2$ is at most $$\left\lceil\frac{k/2}{\sqrt{k/2}}\right\rceil=\bigg\lceil\sqrt{k/2}\bigg\rceil.$$