# nonnegative integer

• Sep 30th 2010, 06:57 AM
lm6485
nonnegative integer
prove that given a nonnegative integer n, there is a unique nonnegative integer m such that m^2 less than or equal to n less than (m+1)^2
• Sep 30th 2010, 07:05 AM
Plato
Quote:

Originally Posted by lm6485
prove that given a nonnegative integer n, there is a unique nonnegative integer m such that m^2 less than or equal to n less than (m+1)^2

The floor function has the property that $\displaystyle \left\lfloor {\sqrt n } \right\rfloor \leqslant \sqrt n < \left\lfloor {\sqrt n } \right\rfloor + 1$
• Sep 30th 2010, 08:20 AM
emakarov
This response is best in practice, but having encountered this problem in my research, I'd like to show a "conceptually-minimal" proof. The thing is that square root involves real numbers, and they are pretty complex objects since they are infinite. My proof uses only logic and properties of natural numbers, including induction.

So, suppose n is given. Towards contradiction, we assume that for every m, it is not the case that m^2 <= n < (m + 1)^2. Then we prove that for all m, m^2 <= n. We do it by induction.

Obviously, 0^2 <= n. Suppose that for some m, m^2 <= n, and we need to show that (m + 1)^2 <= n. Well, if n < (m + 1)^2, then we have m that contradicts our assumption in the previous paragraph.

Having proved that m^2 <= n for all n, we now get a contradiction by instantiating m with, say, n + 1.