Results 1 to 3 of 3

Math Help - Question

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    32

    Question

    Prove that given a nonnegative integer n, there is a unique nonnegative integer m such that m^2≤n<(m+1)^2

    I started like this:

    There are two cases to consider: either n is a perfect square or it is not.

    Case 1:
    Assume n is a perfect square. For the existence part of the proof, let m=√n, where √n is a positive root of n. Then (√n)^2=n, so (√n)^2≤n. Assume for reductio that n≥(√n+1)^2. Factor the right hand side of the inequality and get n≥n+2√n+1. Therefore -1≥2√n, and -1/2≥√n. But √n is a positive root, so we have a contradiction.
    Therefore

    (i) (√n)^2≤n<(√n+1)^2.

    So there exists an m such that m^2≤n<(m+1)^2.

    Now I prove that m is unique. I do this by showing that m cannot be greater or less than √n. To show it is not greater, assume without loss of generality that there is a nonnegative integer m' such that m'=m+1. Therefore, m'=√n+1. Then, for reductio, assume (√n+1)^2≤n<(√n+1+1)^2. The left side of the inequality, (√n+1)^2≤n, contradicts the right hand side of (i): n<(√n+1)^2.

    Now assume that there is a nonnegative integer m' such that m'=m-1. So, m'=√n-1. Now assume (√n-1)^2≤n<(√n-1+1)^2. The right side becomes n<(√n)^2 or n<n, which is a contradiction. Thus, m is unique.

    How do I show this for the case where n is not a perfect square? I know that if n is not a perfect square, then m^2≠n, so I have to prove m^2<n<(m+1)^2. I don't know where to go from here though.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by quiney View Post
    Prove that given a nonnegative integer n, there is a unique nonnegative integer m such that m^2≤n<(m+1)^2

    I started like this:

    There are two cases to consider: either n is a perfect square or it is not.

    Case 1:
    Assume n is a perfect square. For the existence part of the proof, let m=√n, where √n is a positive root of n. Then (√n)^2=n, so (√n)^2≤n. Assume for reductio that n≥(√n+1)^2. Factor the right hand side of the inequality and get n≥n+2√n+1. Therefore -1≥2√n, and -1/2≥√n. But √n is a positive root, so we have a contradiction.
    Therefore

    (i) (√n)^2≤n<(√n+1)^2.

    So there exists an m such that m^2≤n<(m+1)^2.

    Now I prove that m is unique. I do this by showing that m cannot be greater or less than √n. To show it is not greater, assume without loss of generality that there is a nonnegative integer m' such that m'=m+1. Therefore, m'=√n+1. Then, for reductio, assume (√n+1)^2≤n<(√n+1+1)^2. The left side of the inequality, (√n+1)^2≤n, contradicts the right hand side of (i): n<(√n+1)^2.

    Now assume that there is a nonnegative integer m' such that m'=m-1. So, m'=√n-1. Now assume (√n-1)^2≤n<(√n-1+1)^2. The right side becomes n<(√n)^2 or n<n, which is a contradiction. Thus, m is unique.

    How do I show this for the case where n is not a perfect square? I know that if n is not a perfect square, then m^2≠n, so I have to prove m^2<n<(m+1)^2. I don't know where to go from here though.
    Seems you can save yourself some trouble by stating at the beginning, let m=\lfloor\sqrt{n}\rfloor, and then we know that m \le \sqrt{n} \implies m^2 \le n, also m+1>\sqrt{n} \implies (m+1)^2>n, and we are done. (There are some details that can be filled in, but that's basically it.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    It might interest you to know that by coincidence I found this theorem used in a real application just now. GMP is a free library for arbitrary precision arithmetic (bignums) for C. I was looking through the source code file /gmp-5.0.1/mpf/sqrt.c and therein is an argument for why desired precision is achieved through the specified truncation using this theorem in the proof.

    "Further limbs below the 2*prec or 2*prec-1 used don't affect the result and are simply truncated. This can be seen by considering an integer x, with s=floor(sqrt(x)). s is the unique integer satisfying s^2 <= x < (s+1)^2. Notice that adding a fraction part to x (ie. some further bits) doesn't change the inequality, s remains the unique solution. Working suitable factors of 2 into this argument lets it apply to an intended precision at any position for any x, not just the integer binary point."

    Edit: This appears to be the algorithm implemented

    Info: (gmp) Square Root Algorithm
    Last edited by undefined; August 10th 2010 at 09:18 AM.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum