1. Limited time only! Sign up for a free 30min personal 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!

Square numbers between n and 2n -- Check my proof please

  1. Aug 21, 2015 #1
    I noticed that for any integer greater than 4 there exists at least one perfect square in the open interval (n, 2n). I think I have proved the statement, but as I am not a professional, I'd like someone to review my proof.

    By induction we see that it is true for [itex]n=5[/itex] because [itex]5<9<10[/itex].

    Now suppose that it is true for n, and let's prove it for n + 1.
    From the inductive hypothesis we know that there is an x such that [itex]n<x^2<n+1[/itex]. This square should work for n + 1 too. Like in the case of [itex]n=5[/itex] the square 9 works for 6, 7 and 8 too. But not for [itex]n=9[/itex] or greater. Here we need the next square 16.

    So if [itex]x^2\ge n+1[/itex] we must show that [itex](x+1)^2[/itex] is the square we need. In other words we have to verify that
    [tex]n+1<(x+1)^2<2(n+1)[/tex]
    Notice that for positive n, if [itex]x^2\le n+1[/itex] then [itex]x\le \sqrt{n+1}[/itex]. As [itex]n<x^2[/itex] it follows that
    [tex]n+1<x^2+1<x^2+2x+1=(x+1)^2[/tex]
    We have to show that [itex](x+1)^2<2(n+1)[/itex]
    [tex](x+1)^2=x^2+2x+1<\left(n+1\right)+2\sqrt{n+1}+1[/tex]
    [tex]\left(n+1\right)+2\sqrt{n+1}+1 < 2(n+1)[/tex]
    [tex]n^2-4n-4>0\rightarrow n>2\sqrt 2 + 2\rightarrow n\ge 5[/tex]
    So we proved that for any [itex]n\ge 5[/itex] there is at least one x such that [itex]n< x^2 < 2n[/itex].
     
  2. jcsd
  3. Aug 21, 2015 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    The statement is true, but the proof looks more complicated than necessary - you don't need mathematical induction. All you need is (similar to what you have) is [itex] n\gt 2\sqrt{n} + 1[/itex] for n > 4.
     
  4. Aug 21, 2015 #3

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Looks like Your 4th sentence is false to start with.
    ##x^2 \geq n+1## ... consider n=8, interval is 9,10,11,12,13,14,15,16,17 .... there are two squares in the interval.
    7th sentence... try verifying the statement by example... n=5
    Then the expression asserts that 6<100<12 ... which is false.

    At best you need to tidy up your notation.

    By induction, you want to assume: ##\exists x\in\mathbb Z: n <x^2<2n## is true, then prove
    ##\exists x\in\mathbb Z: n+1 <x^2<2n+2## .
     
  5. Aug 21, 2015 #4
    No, you want to assume: ##\exists x \in\mathbb Z: n <x^2<2n## is true, then prove ##\exists y \in\mathbb Z: n+1 <y^2<2n+2## . Most of the time you can take y=x and this is trivial, but it doesn't always work.
     
  6. Aug 22, 2015 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    In fact, you can always find ##x## such that:

    ##\sqrt{n} < x \le \sqrt{n}+1##

    This ##x## does the job unless ##6n \ge n^2 + 1##, which only holds for ##n < 6##

    Then you can check ##n = 5## manually.
     
    Last edited: Aug 22, 2015
  7. Aug 22, 2015 #6

    mathman

    User Avatar
    Science Advisor
    Gold Member

    My previous note is in error. The key expression should be [itex]\lfloor \sqrt{n} \rfloor +1 \lt \lceil \sqrt{2n} \rceil [/itex].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Square numbers between n and 2n -- Check my proof please
  1. Squaring numbers (Replies: 6)

Loading...