Prove that given a nonnegative integer $n$, there is a unique nonnegative integer $m$ such that $(m-1)^2 ≤ n < m^2$

Question

Prove that given a nonnegative integer $n$, there is a unique nonnegative integer $m$ such that $(m-1)^2 ≤ n < m^2$

My first guess is to use an induction proof, so I started with n = k = 0:

$(m-1)^2 ≤ 0 < m^2 $

So clearly, there is a unique $m$ satisfying this proposition, namely $m=1$.

Now I try to extend it to the inductive step and say that if the proposition is true for any $k$, it must also be true for $k+1$.

$(m-1)^2 + 1 ≤ k + 1 < m^2 + 1$

But now I'm not sure how to proof that. Any ideas?

Answer 1

It's nicer to prove for $$m^2 \le n < (m+1)^2$$ which is obviously equivalent.

so take the square root: $$m \le \sqrt{n} < m+1$$

from this you can see $m=\lfloor{\sqrt{n}}\rfloor$ is the unique $m$.

Answer 2

I am not sure whether the proof by induction is worth being done here - it's much more easier to show it in general. Let $(a_m)_{m\in \Bbb N_0}$ be a monotonically increasing and unbounded sequence. By unboundness, for any $n$ there exists $k\in \Bbb N_0$ such that $n<a_k$ and thus we can define $$ m(n) = \min\{k\in \Bbb N_0:n<a_k\}. $$ Clearly, $a_{m(n)-1}\leq n$ as otherwise we would come to a contradicition with the definition of $m(n)$ since the sequence $a_m$ is increasing. Thus $m(n)$ is the unique number such that $$ a_{m(n)-1}\leq n<a_{m(n)}. $$ Just take now $a_m = m^2$.

Answer 3

Try breaking it up into cases, depending on whether $k < m^2 - 1$ or $k = m^2 - 1$. If the former holds, then show that $(m-1)^2 \leq k+1 < m^2$. Otherwise, show that $m^2 \leq k+1 < m^2 +1 \leq (m+1)^2$.

Answer 4

Given $n\ge0$ (and not even necessarily an integer), let $S=\{m\in\mathbb N_0\mid m^2>n\}$ Then the set $S$ is a nonempty (why?) subset of $\mathbb N_0$ and hence contains a smallest element $m_0$. Then $m_0^2>n$ because $m_0\in S$. Then clearly $m_0\ne 0$ because $m_0^2>n\ge 0$, hence $m_0-1\in\mathbb N_0$. But by minimality of $m_0$, we have $m_0-1\notin S$, hence $(m_0-1)^2<n$.

Assume that also $(m_1-1)^2<n\le m_1^2$ for some $m_1\ne m_0$. Then $m_1>m_0$ by minimality of $m_0$. Then from $(m_1-1)^2-m_0^2=(m_1+m_0-1)(m_1-m_0-1)\ge 0$, we conclude $(m_1-1)^2\ge m_0^2>n$ - contradiction.

Remark: Let $f\colon \mathbb N_0\to \mathbb R$ be any strictly monotonuosly increasing and unbouned function. Then for each $a\in\mathbb R$ with $a\ge f(0)$ there exists a unique $m\in\mathbb N$ such that $f(m-1)\le a<f(m)$.