# Prove by contradiction that for every positive integer $k$, there is an integer $m$ such that $k\leq m^2\leq2k$

Prove by contradiction that for every positive integer $k$, there is an integer $m$ such that $k\leq m^2\leq2k$.

Heres what I've done.

Take the negation of the statement above to attempt a contradiction. We have "There exist a positive integer $k$ such that for all integers $m$, $k>m^2$ or $m^2>2k$". We have the following cases.

Case 1: $k>m^2$ but $m^2\not>2k$

We have $k>m^2$ and $m^2\leq2k$, which implies that $m^2<k\leq2k$.

Case 2: $k\not>m^2$ but $m^2>2k$

We have $m^2>2k$ and $m^2\leq k$, which implies that $2k<m^2\leq k$ implying $2k<k$ whch is impossibru as $k\geq 1$. Therefore contradiction.

Case 3: $k>m^2$ and $m^2>2k$

We have $k>m^2$ and $m^2>2k$, which implies $2k<m^2<k$ implying $2k<k$ whch is impossibru as $k\geq 1$. Therefore contradiction.

Actually thats the furthest I could go. Any hints or perhaps solutions?

Ok I Edited as I got new epihany from some ideas. Now I left with contradicting Case 1.

-

Your case 1 states "There exists a positive integer $k$ such that for all integers $m$, $m^2 < k \leq 2k$." The second inequality is meaningless so we get rid of that. This leaves

"There exists a positive integer $k$ such that for all integers $m$, $m^2 < k$."

I will show this is not possible. Okay, so take ANY integer $k$. If $k \leq 0$, then $m^2 \geq 0$ and therefore $m^2 < k$ is false. So, assume $k > 0$. Now, choose $m = k+1$. Then $m^2 = k^2 + 2k + 1 = k + (k^2 + k + 1) > k$.

-
Yup i think so. I mean, why not? –  Yellow Skies Oct 1 '12 at 18:07
@SingaporeanDude. for all integers –  user39572 Oct 1 '12 at 18:08
mmmhmm. Say m=0, then k could be 1. Say m=-30, $m^2$=900, and k could still be bigger. Still can't see your point hehe. –  Yellow Skies Oct 1 '12 at 18:10
@SingaporeanDude. the point is there will always exist a $k$ that is larger than $m^2$. If I give you an integer, you can always pick a bigger one (by adding 1 for instance, as Graphth pointed out). Basically if there did exist such a $k$, it would have to be larger than all possible integers. Contradiction. –  user39572 Oct 1 '12 at 18:11
@Graphth Yeah! why not? in your example, k is always bigger then $m^2$ –  Yellow Skies Oct 1 '12 at 18:12

ok because we have not constraint,we can say that for $k>0$; $k<2*k$,now if $m<0$ then $m^2>2*m$;else $2*m<=m^2$;now let us return to problem statment, suppose that $k>m^2$ always hold,this is not always because we can easily find value for $k$ and $m$,for which $k <=m^2$ ;because we used fact that for $k>0$ ;$k<2*k$;we have to show that $k>m^2$ and $m^2>2*k$ or $k>m^2$ and $m^2<2*k$ at the same time;but first is false,and second we can always find value for $k$ and $m$ ,such that second condition does not hold,so i think my argument is correct

-

Here's an alternative solution. We take advantage of the gap between consecutive squares. Suppose that for some $k$ there exists no squares between $k$ and $2k$. Let $m$ be the largest integer such that $m^2 < k$. Then we must have $$m^2 < k < 2k < (m+1)^2$$ In particular this means that the gap between $(m+1)^2$ and $m^2$ is greater than $k$. $$(m+1)^2 - m^2 = 2m+1 > k$$ Clearly $m\neq 1$. Then $m\ge 2$. But that means $$2m \le m^2 < k \implies 2m + 1 \le k$$ There is our desired contradiction.

-

Hint $\rm\ f(x) = x^2$ is increasing, $\rm\:f(x + 1) < 2\,f(x)\:$ for $\rm x\ge 3\:$
thus $\rm\:f(m) < k\le f(m\!+\!1)\:\Rightarrow\:f(m\!+\!1) < 2\,f(m) < 2k$

-