Prove that the $n$th positive nonsquare integer is $n+\{ \sqrt{n} \}$ where $\{x\}$ is denotes the integer closest to $x$. For any positive integer $n$, let $f(n)$ denote the $n$th positive nonsquare integer, i.e.,

*

*$f(1)=2$

*$f(2)=3$

*$f(3)=5$

*$f(4)=6$

*etc.

Prove that $f(n)=n+\{ \sqrt{n} \}$ where $\{x\}$ denotes the integer closest to $x$ (for example, $\{\sqrt{1}\}=1$, $\{\sqrt{2}\}=1$, $\{\sqrt{3} \}=2$, $\{\sqrt 4 \}=2$,...)
 A: This was fun! Thanks for asking it ^_^
The key observation is this:
$$f(n^2) = n^2 + n$$
After all, there are $n$ squares $\leq n^2$ that we had to skip along the way.
I'll write this somewhat more suggestively as
$$f(n^2) = n^2 + \left \{ \sqrt{n^2} \right \}.$$
Now let's see what happens as we increment $n^2$. We want to understand what happens everywhere between $f(n^2)$ and $f((n+1)^2) = f(n^2 + 2n + 1)$. So we want to look at $f(n^2 + k)$ for $1 \leq k < 2n + 1$.
The next square happens at $(n+1)^2 = n^2 + 2n + 1$, which is $n+1$ steps away from $f(n^2)$. So we'll split this region into two pieces:

*

*First we'll look at $1 \leq k < n+1$

*Then we'll look at $n+1 \leq k < 2n+1$

For $k < n+1$, we have no fears! We don't see any more square numbers, and this makes counting the nonsquares particularly easy:
$$f(n^2 + k) = f(n^2) + k = n^2 + k + n$$
So we're led to a natural question: For $k < n+1$
$$n \overset{?}{=} \left \{ \sqrt{n^2+k} \right \}$$
And the answer is easily seen to be yes. Intuitively, this is because $n^2+n$ is closer to $n^2$ than it is to $(n+1)^2$. I'll leave it to you to formalize the argument. (As a hint: $\sqrt{n^2 + n} = n \sqrt{1 + \frac{1}{n}}$, and you might imagine $\sqrt{1 + \frac{1}{n}}$ doesn't change the value when we round to the nearest integer).

For $n+1 \leq k < 2n+1$, we've seen exactly one new square. So
$$f(n^2 + k) = f(n^2) + k + 1 = n^2 + k + n + 1$$
Again, you see the question coming: For $n+1 \leq k < 2n+1$
$$n + 1 \overset{?}{=} \left \{ \sqrt{n^2 + k} \right \}$$
And again, it's easy to see the answer is yes. This is (intuitively) because $n^2 + n + 1$ is now closer to $(n+1)^2$ than to $n^2$. You can do a similar manipulation to my previous hint to formalize this intuition.

I hope this helps ^_^
