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