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

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer
    
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
1  
@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

share|improve this answer

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.

share|improve this answer

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$

share|improve this answer

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.