Number of integer solutions to x^2 + y^2 <= n? [simple proof]

[nickadams]

Homework Statement

I am stuck on a step from a simple proof in Gelfand's method of coordinates.
Here is a link to the part I am confused on. Pg. 44-45...
http://books.google.com/books?id=In...ether with an estimate of its error:"&f=false

It starts in the middle of page 44 and ends right below the part I have highlighted on page 45.

Homework Equations

pi*r^2 is area of a circle.
2*pi*r is the circumference of a circle.
diagonal of a 1 unit^2 square is √(2) units
distance formula is (x1-x2)^2 + (y1-y2)2 = d^2

The Attempt at a Solution

when it asked to prove that "the figure A_n lies entirely within the circle K_n'' and contains the circle k_n' entirely within itself," I came up with an attempt by making a triangle ABC with A at (0,0), B at (B_x,0) and C at (0,C_y) and saying AB + AC < BC

next, using the distance formula, I changed AB to B_x², AC to C_y² , and BC to B_x² + C_y²... That would mean that B_x² + C_y² < B_x² + C_y² which is clearly impossible! Does that qualify as a proof?

So since K_n'' has a radius that is √(2) bigger than K_n, then if the upper right vertex of a unit square is within the circumference of K_n, then it must also be within the circumference of K_n''. Because in order for it to extend beyond the circumference of K_n'' while still remaining in the circumference of K_n, then it would have to take up a distance larger than √(2) which is not possible for a 1 unit square. Same goes for K_n' not being completely within A_n because that would mean that one part of a unit square was inside the circumference of K_n' while the upper right hand corner of the same square was out of K_n... Not possible unless it had a straight line distance within the unit square that was longer than √(2).
OOOkay. Now that we have that part out of the way (hopefully it's right), the part I'm confused on is how they got from all the lead up steps to their final conclusion of:

|N-pi*n| < 2*pi(√(2n) + 1)

... I think they are trying to quantify the difference between the unit squares in A_n and the actual area of circle K_n. So they set minimum and maximum boundaries (K_n' and K_n'' respectively) that can help out. K_n' tells us the smallest circular boundary where A_n will stay within and K_n'' gives us the largest circle that will still be completely filled by A_n.

But I'm stuck on how they got the right side of the above inequality... All help will be appreciated; sorry for the long post!

 

[dodo]

Hi, Nick,
I have not read in detail your proof, but if you're already convinced than the figure A_n (made of N squares) is entirely contained inside the larger circle, and entirely contains the smaller circle, then it should be clear to you the inequality in the book (just before your highlighting) that expresses the relationship between the areas of these three figures:\pi(\sqrt n - \sqrt 2)^2 &lt; N &lt; \pi(\sqrt n + \sqrt 2)^2
Starting from there, expand the squares to obtain\pi(n - 2\sqrt {2n} + 2) &lt; N &lt; \pi(n + 2\sqrt {2n} + 2)
and now distribute the \pi along the parentheses,\pi n - 2\pi\sqrt {2n} + 2\pi &lt; N &lt; \pi n + 2\pi\sqrt {2n} + 2\pi
subtract \pi n all through,-2\pi\sqrt {2n} + 2\pi &lt; N - \pi n &lt; 2\pi\sqrt {2n} + 2\pi
factor out the common 2\pi,-2\pi(\sqrt {2n} - 1) &lt; N - \pi n &lt; 2\pi(\sqrt {2n} + 1)
and now, as \sqrt {2n} + 1 is a larger positive quantity than \sqrt {2n} - 1 whenever n &gt; 0, you might have just as well said-2\pi(\sqrt {2n} + 1) &lt; N - \pi n &lt; 2\pi(\sqrt {2n} + 1)
which is equivalent to|N - \pi n| &lt; 2\pi(\sqrt {2n} + 1)
So, as you see, it's just some algebra, an almost mechanical "operations on symbols", that take you from one inequality to the other.

Hope this helps!

 

[nickadams]

Oh wow thanks Dodo!

But I got stuck on this part of your response...

-2\pi(\sqrt {2n} - 1) &lt; N - \pi n &lt; 2\pi(\sqrt {2n} + 1) and now, as \sqrt {2n} + 1 is a larger positive quantity than \sqrt {2n} - 1 whenever n &gt; 0, you might have just as well said-2\pi(\sqrt {2n} + 1) &lt; N - \pi n &lt; 2\pi(\sqrt {2n} + 1)
which is equivalent to|N - \pi n| &lt; 2\pi(\sqrt {2n} + 1)

How were you able to change -2\pi(\sqrt {2n} - 1) to -2\pi(\sqrt {2n} + 1) ?

Thanks again

 

[Wizlem]

How were you able to change -2\pi(\sqrt {2n} - 1) to -2\pi(\sqrt {2n} + 1) ?

-2\pi\sqrt {2n} - 2\pi &lt; -2\pi\sqrt {2n} + 2\pi

and so

-2\pi(\sqrt {2n} + 1) &lt; -2\pi(\sqrt {2n} - 1)

and you still know -2\pi(\sqrt {2n} + 1) &lt; N - \pi n

 

[dodo]

Hi, Nick,
Wizlem gave you the details, above. The general idea is that, for example, if you know that a number is between -5 and 6, you can also say that it is between -6 and 6... because the latter interval is larger and includes the former. Then, having chosen a symmetric interval, we can now say that our number is no greater than 6 in absolute value. The principle in your case is the same.