3
$\begingroup$

I am trying to prove $$\lim_{n\to\infty} \frac{n-\lfloor \sqrt n \rfloor^2}{n} = 0$$ given $n>0$.

But I'm having difficulties dealing with the floor function. I tried splitting apart the limit like so:

\begin{align*} \lim_{n\to\infty} \frac{n-\lfloor \sqrt n \rfloor^2}{n} &= \frac{\lim_{n\to\infty} (n-\lfloor \sqrt n \rfloor^2)}{\lim_{n\to\infty} n} \\ &= \frac{\lim_{n\to\infty} n}{\lim_{n\to\infty} n} - \frac{\lim_{n\to\infty} \lfloor \sqrt n \rfloor^2}{\lim_{n\to\infty} n} \end{align*}

Trivially $\lim_{n \to \infty} \lfloor \sqrt n \rfloor^2 = \infty$, but it seems to grow somewhat slower than $\lim_{n \to \infty} n$ and so I am not sure if it is correct to conclude that $$\frac{\lim_{n\to\infty} \lfloor \sqrt n \rfloor^2}{\lim_{n\to\infty} n} = 1.$$

$\endgroup$
6
$\begingroup$

Using $$x-1<\lfloor x \rfloor \le x$$ $$\lim_{n\to\infty} \frac{n-(\sqrt n)^2}{n}\le\lim_{n\to\infty} \frac{n-\lfloor \sqrt n \rfloor^2}{n}\le\lim_{n\to\infty} \frac{n-(\sqrt n-1)^2}{n}$$ $$0\le\lim_{n\to\infty} \frac{n-\lfloor \sqrt n \rfloor^2}{n}\le\lim_{n\to\infty} \frac{2\sqrt n-1}{n}=0$$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

For very large values of $n$, the floor of $\sqrt{n}$ is almost indistinguishable (in the relative sense) from $\sqrt{n}$ itself; the absolute difference is at most $1$, so the relative difference is tending to zero.

To make this precise, note that we have the inequalities

$$\sqrt{n} - 1 \le \lfloor \sqrt{n} \rfloor \le \sqrt{n}$$ Thus upon squaring,

$$n - 2\sqrt{n} + 1 \le \lfloor \sqrt{n}\rfloor^2 \le n$$

After some algebraic work, you should be able to reduce the problem to computing $\lim_{n \to \infty} \sqrt{n} / n$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Another possibility:

$$\frac{n-\lfloor \sqrt n \rfloor ^2}{n} \leq \frac{\lceil \sqrt{n} \rceil^2 - \lfloor \sqrt n \rfloor ^2}{n} = \frac{(\lceil \sqrt{n} \rceil - \lfloor \sqrt n \rfloor)(\lceil \sqrt{n} \rceil + \lfloor \sqrt n \rfloor) }{n} \leq \frac{2 \lceil \sqrt{n} \rceil}{n} \to 0.$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The lowest that $\lfloor\sqrt n\rfloor$ can be is $\sqrt n - 1$. Hence we have

$$n - \lfloor\sqrt n\rfloor^2 > n - (n - 2\sqrt n +1) = 2\sqrt n - 1$$

So the above divided by $n$ tends to zero.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.