Prove there is a perfect square between n and 2n

  • #1
435
13

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.
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
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
435
13
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
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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 [itex]m^2[/itex] 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 [itex]k< m_k^2\le 2k[/itex], show that there must be an integer, [tex]m_{k+1}[/tex], such that [tex]k+ 1< m_{k+1}^2\le 2(k+1)[/tex]
 
  • #5
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,828
5,601
Now, assuming that, for integer k, there exist integer [itex]m_k[/itex] such that [itex]k< m_k^2\le 2k[/itex], show that there must be an integer, [itex]m_{k+1}[/itex], such that [tex]k+ 1< m_{k+1}^2\le 2(k+1)[/tex]
I think you need each of those less thans to be less-than-or-equal-tos.
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,833
956
Yes, I misread the original post.
 
  • #7
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
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.
 
  • #8
435
13
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?
 
  • #9
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,828
5,601
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.
 
  • #10
435
13
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,828
5,601
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<=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
435
13
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,828
5,601
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.
 
  • #14
435
13
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
435
13
If m^2=n then that is a separate case right?
 
  • #16
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
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##.
 
  • #17
435
13
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
435
13
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
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

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.
 
  • #21
435
13
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?
 
  • #22
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
Using the inequality, what must ##m^2+2m## be less than or equal to?
 
  • #23
435
13
## 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
 
Last edited:
  • #24
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
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?
 
  • #25
435
13
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##
 
Last edited:

Related Threads on Prove there is a perfect square between n and 2n

  • Last Post
Replies
14
Views
16K
  • Last Post
Replies
3
Views
3K
Replies
7
Views
12K
Replies
4
Views
3K
  • Last Post
Replies
6
Views
1K
Replies
14
Views
781
  • Last Post
Replies
4
Views
8K
Top