Prove there is a perfect square between n and 2n

[Panphobia]

Homework Statement

Prove that for all natural numbers n, there exists a natural number m^2 such that
n ≤ m^2 ≤ 2n

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.

 

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

 

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

 

[HallsofIvy]

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 [itex]m_k[itex] such that $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)$$

 

[haruspex]

Now, assuming that, for integer k, there exist integer $m_k$ such that $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)$$

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

 

[HallsofIvy]

Yes, I misread the original post.

 

[andrewkirk]

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 ne

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.

 

[Panphobia]

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.

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?

 

[haruspex]

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?

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

 

[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?

 

[haruspex]

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?

Not sure what Andrew had in mind with the hint. Maybe this: Given that n<=m²<=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?

 

[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

 

[haruspex]

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

Yes.

 

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

 

[Panphobia]

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

 

[andrewkirk]

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

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

 

[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)

 

[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?

 

[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?

 

[Ray Vickson]

Homework Statement

Prove that for all natural numbers n, there exists a natural number m^2 such that
n ≤ m^2 ≤ 2n

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.

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.

 

[Panphobia]

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?

I think the equality was $m \geq 2$ I don't see how that can help, yes you can sub in a value for m that is less than 2 and preserve the inequality but I don't know why that would help?

 

[andrewkirk]

Using the inequality, what must $m^2+2m$ be less than or equal to?

 

[Panphobia]

$m^2 + 2m \geq 8$ and then you still get $8 \leq 2n$. Am I supposed to show that $m^2 + 2m$ is less than something else to show that it is also less than or equal to $2n$? I don't know what to use, usually you're supposed to use the induction hypothesis somehow, but I can't see it in this problem

 

[andrewkirk]

I didn't ask what $m^2+2m$ is greater than or equal to. I asked what it was less than or equal to. What can you say that $m^2+2m$ is less than or equal to, using the inequality?

 

[Panphobia]

The condition on m is that $m^2 = n$ or $m = \sqrt n$ so $m^2 + 2m \leq n + 2 \sqrt n$? Can't I just prove it for all n=1,2,3 and then just use what I showed for n>=4? Or $(m+1)^2 = m^2 + 2m + 1 \leq m^2 + m^2 +1 \leq 2n+2$