Source: American Mathematical Monthly (1988)
Observation: If holds , then it must hold , since .
To show that holds , we can use the definition of the floor function:
Thus, we can re-write the original question in the following format:
Combining the two error terms into one and move it to the right hand side of the equation, we obtain:
Our search has now become: show that for all , for . In other words, if we find the minimum and the maximum of the left hand side and conclude that it's bounded between , we would be done.
To find the extrema of the left hand side, we need to take the first-order derivative and set it equal to zero:
And the solution to this is , which, when plugged back into the original equation, gives a maximum value of , which is indeed less than . Because is monotonically increasing simply by observation and is monotonically decreasing by observation, we can be sure that is the only extreme point in .
To find the minimum, we check the edge point because the first-order derivative would not help us there. At , we get , which is indeed greater than .
The proof is complete (that is, if you believe that I have found all critical values of such as or whatever).
I was originally going to try to use induction, as the phrase "for all in the naturals" seemed to suggest, but the square roots really gave me trouble because I could not free up my and terms; it was a serious mess. Anyone have better luck with this?