Prove there is a perfect square between n and 2n

Tags:
1. Oct 1, 2015

Panphobia

1. The problem statement, all variables and given/known data
Prove that for all natural numbers n, there exists a natural number m^2 such that
n ≤ m^2 ≤ 2n

3. The attempt at a solution

I know how to prove this directly or by construction but my professor wants it solved by induction. When you're solving something by induction you have to show that for some statement p(n), p(n) → p(n+1). But in this problem how would I even start, if I start with the above inequality I can't seem to get it of the form n+1.

2. Oct 1, 2015

andrewkirk

Start with n=1. Then the square is $1^2$.
Then try to prove that, if there's a square between n and 2n, there must be a square between (n+1) and 2(n+1).

You may need to prove it for n=2 as well before you try the induction step. Then you can use an additional premise than $m\geq 2$, which may be useful.

3. Oct 2, 2015

Panphobia

If I start with the inequality how can I add one to the left side and 2 to the right side? That is how you usually prove things, I just have no idea where to start, I have done the base case but other than that I have no idea what to do next.

4. Oct 2, 2015

HallsofIvy

Staff Emeritus
Your basic problem is that what you are trying to prove isn't true. If n= 1, 2n= 2 and there is no integer, m, such that $m^2$ is between 1 and 2!
Do you mean to require that n is at least 2?

No one is saying to "add one to the left side and 2 to the right side". andrewkirk is suggesting that you use "proof by induction". first, prove this is true for n= 2. With n= 2, 2n= 4 and 4 is itself a perfect square. Now, assuming that, for integer k, there exist integer $m_k[itex] such that [itex]k< m_k^2\le 2k$, show that there must be an integer, $$m_{k+1}$$, such that $$k+ 1< m_{k+1}^2\le 2(k+1)$$

5. Oct 2, 2015

haruspex

I think you need each of those less thans to be less-than-or-equal-tos.

6. Oct 2, 2015

HallsofIvy

Staff Emeritus
Yes, I misread the original post.

7. Oct 2, 2015

andrewkirk

Do two base cases first, for n=1 and n=2. The corresponding values of m are 1 and 2.
Then prove the induction step, which is:

For any integer $n\geq 1$ If there exists integer $m\geq 2$ such that $n\leq m^2\leq 2n$, there exists an integer $r$ such that $n+1\leq r^2\leq 2(n+1)$.

Hint: Use the fact that the ranges $n$ to $2n$ and $n+1$ to $2(n+1)$ mostly overlap.

8. Oct 2, 2015

Panphobia

But for n = 1, m has to be 1 so the whole m>=2 is wrong, then it would have to be n>=2 right? Or am I overlooking something?

9. Oct 2, 2015

haruspex

Andrew is saying that when n=1 m=1, and when n=2 m=2.

10. Oct 2, 2015

Panphobia

Would I then split it up into cases where they overlap and where they don't? Then try to prove that where they don't overlap (m+1)^2 exists in the range?

11. Oct 2, 2015

haruspex

Not sure what Andrew had in mind with the hint. Maybe this: Given that n<=m2<=2n, what is an obvious possibility for a square between n+1 and 2n+2? When that does not work, what would your next candidate be?

12. Oct 2, 2015

Panphobia

An obvious possibility is that n+1 <= m^2 <= 2n+2 and when that doesn't hold it would be n+1 <= (m+1)^2 <= 2n+2

13. Oct 2, 2015

haruspex

Yes.

14. Oct 2, 2015

Panphobia

The only time m wouldn't satisfy the equation would be when n +1 <= m^2 <= 2n, does this hold any significance? I am sorry but I have never done an inductive proof with more than one variable so I am kind of just guessing.

15. Oct 2, 2015

Panphobia

If m^2=n then that is a separate case right?

16. Oct 2, 2015

andrewkirk

That's right. We have $n\leq m^2\leq 2n$ and if $m^2\geq n+1$ then we can just use $m$ again for our square in the range $n+1$ to $2(n+1)$. The only case where that doesn't work is where $m^2=n$.

Now since in that case $m$ is too small, what's the next smallest number that we are going to try squaring? Square that number. First prove that the square is more or equal to $n+1$ - which is trivial. Then try to prove that the square is less than $2(n+1)$. This is where you are going to use that extra assumption than $m\geq 2$.

17. Oct 3, 2015

Panphobia

So for proving the square is more than or equal to n+1 this is how I did it n+1 <= m^2 + 1 <= m^2 + 2m + 1 = (m+1)^2. Then for trying to prove that the square is less than or equal to 2(n+1), I am trying to somehow show that m^2 + 2m <= 2n because m = sqrt(n), and this works for all m>=2, then we can have m^2+2m+1=(m+1)^2<=2n+1<=2(n+1)

18. Oct 3, 2015

Panphobia

For the m^2 + 2m <= 2n do I need to show that n>=2*sqrt(n)? Then wouldn't it just factor into n(n-4)>=0 so n>=4 for this to even work. I don't understand when this already works for n=1,2, and 3. Am I missing something?

19. Oct 3, 2015

andrewkirk

You need to show that $m^2+2m\leq 2n$. Do you remember the special extra condition on $m$ that we did the extra base case $n=2, m=2$ in order to obtain? What was that condition. If it's an inequality involving $m$, how can it help here?

20. Oct 3, 2015

Ray Vickson

If you assume that there exists integer $m= m_n$ such that $n \leq m^2 \leq 2n$, then the induction step is easy if $m > n$, because if $n < m^2 \leq 2n$ then $n+1 \leq m^2 < 2(n+1)$. The only remaining case is when $n = m^2$. Can you deal with the induction step in that case?

Note added in edit: the post #16 already said all this, but did not appear on my screen until after I posted this current message. I have often found that type of delay occurring in this forum.