Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

5 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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)$.

share|improve this answer
add comment

Its too late to answer the question but if it helps you can prove it by contradiction also.

Assume that there exists a k such that k is less than m. so

(k−1)2≤n< k2

The smallest k which is possible is k = m-1. Then we have

(m-2)2 ≤ n< (m-1) 2

which is contradicting the assumed statement. so the solution has a unique value.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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