1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove there is a perfect square between n and 2n

Tags:
  1. Oct 1, 2015 #1
    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. jcsd
  3. Oct 1, 2015 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Oct 2, 2015 #3
    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.
     
  5. Oct 2, 2015 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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]
     
  6. Oct 2, 2015 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I think you need each of those less thans to be less-than-or-equal-tos.
     
  7. Oct 2, 2015 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, I misread the original post.
     
  8. Oct 2, 2015 #7

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  9. Oct 2, 2015 #8
    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?
     
  10. Oct 2, 2015 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Andrew is saying that when n=1 m=1, and when n=2 m=2.
     
  11. Oct 2, 2015 #10
    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?
     
  12. Oct 2, 2015 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  13. Oct 2, 2015 #12
    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
     
  14. Oct 2, 2015 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes.
     
  15. Oct 2, 2015 #14
    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.
     
  16. Oct 2, 2015 #15
    If m^2=n then that is a separate case right?
     
  17. Oct 2, 2015 #16

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##.
     
  18. Oct 3, 2015 #17
    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)
     
  19. Oct 3, 2015 #18
    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?
     
  20. Oct 3, 2015 #19

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  21. Oct 3, 2015 #20

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted