Sunday, April 30, 2006

Method of Exhaustion

In today's blog, I go over the proof for Eudoxus's Method of Exhaustion. This proof is used later in Euclid's proof that the areas of circles are in proportion to the squares of their diameters.

Theorem: Method of Exhaustion

Let x,y be any two positive real numbers where x is greater than y. If we continually remove a quantity v ≥ (1/2) from x, then eventually, we will be left with a value that is smaller than y.

Proof:

(1) We will only need to prove this for v = 1/2 since:

(a) This proof is done if we can show that there exists n such that (1/2)n*x is less than y.

(b) We only need to prove it for v=1/2 since we know that if v is less than (1/2), then:

vn*x is less than (1/2)*n*x.

(2) Let m be an integer such that m ≥ x/y + 1

(3) So that ym is greater than x

(a) Since ym is greater than y(x/y + 1) = x + y

(b) and x + y is greater than x since y is nonzero.

(4) There exists a value n such that 2n is greater than m.

(a) Let m = 1

(b) 21 = 2 is greater than 1.

(c) Assume this is true up to n.

(d) So that 2n is greater than n.

(e) Since 2n is greater than 1, we know that:
2n + 2n = 2*(2n) = 2n+1 is greater than n+1.

(f) So that this is true by induction.

(5) Thus, we see that y/x is greater than 1/2n

(a) ym is greater than x (step #2)

(b) so, m is greater than x/y

(c) and 1/m is less than y/x (or in other words, y/x is greater than 1/m)

(d) Now, 2n is greater than m so 1/2n is less than 1/m which also means that it is less than y/x.

(6) Thus (1/2)nx is less than y since y/x is greater than (1/2)n means that y is greater than (1/2)n*m.

QED

Now, let's look at two applications of the Method of Exhaustion.

Lemma 1: If a square is inscribed in a circle, its area is greater than half the area of the circle.





















Proof:

(1) Let EFGH be a square that is inscribed in the circle above (see here for details on this construction).

(2) Let KLMN be a square that is circumscribed around the circle above (see here for details on this construction).

(3) The area of KLMN is greater than the area of the circle.

(4) The square EFGH is equal to (1/2) the area of KLMN since:

(a) Each square KFCE, FLGC, CGMH, ECHN are (1/4) the area of KLMN.

(b) Each triangle EFC, CFG, HCG, ECH is (1/4) the area of EFGH

(c) Each triangle EFC, CFG, HCG, ECH is (1/2) the area of the corresponding square KFCE, FLGC, CGMH, ECHN.

(d) Therefore, area EFGH = (1/2) * area KLMN

(5) Finally, area EFGH = (1/2)* area KLMN which is greater than the area of (1/2) the circle (from step #3).

QED


Lemma 2: For any area A that is smaller than the area of a circle C, there exists a regular polygon P that is smaller than C but greater than A.


























Proof:

(1) Let us form a circle C on the diameter FH. [See here for details on construction]

(2) It is possible to find points E,G such EFGH forms a square that is inscribed in circle C [See here for details on this construction]

(3) The area of the square EFGH is greater than (1/2) the area of circle C [See Lemma 1 above]

(4) We can constructs points K, N, M, and L so that point K is midway between points E and F, N is midway between E and H, M is midway between H and G, and L is midway between G and F. [See here for details on this construction]

(5) Each triangle EKG, FLG, GMH, and HNE is greater in area than half the segment of the circle about it since:

(a) From each triangle, we can construct a rectangle that has an area greater than the circle segment. For example, around triangle EKG we can construct a rectangle as in the diagram above.

(b) Each half of the triangle is exactly 1/4 the size of the rectangle since each point bisects the side of the circumscribed square.

(c) So the triangle EKG is equal to (1/2) the area of the rectangle.

(d) Since the area of the rectangle is greater than the area of the segment, (c) gives us that the triangle EKG is greater than (1/2) the area of the segment.

(6) We can keep repeating this step so that each time, we remove more than (1/2) the area:

(a) We select the midpoints to each of the existing segments. [See step #4 for details]

(b) We form a triangle with these new midpoints from the points of the segment that this new point bisected.

(c) This set of triangles together forms a new regular polygon.

(d) Each triangle has more area than half the circle segment that had previously remained. [This is the same as the argument in step #5]

(11) So, then there eventually exists a polygon EKFLGMHN such that the area of this polygon is greater than the area of S. [From the Method of Exhaustion above since each time we do step #6, we are subtracting greater than 1/2 of the remaining area from the circle.]

QED

Lemma 3: If a regular polygon P1 with area A1 is circumscribed around a circle C, then there exists a smaller polygon P2 with area A2 that can also be circumscribed around circle C such that:

A2 - C is less than (1/2)(A1 - C)


































Proof:

(1) Let C be a circle formed from diameter BD with center E. [See here for details on construction]

(2) Circumscribe a square GHKF around circle C. [See here for details on construction]

(3) Find a point M that lies on circle C and is midway between A and B [See here for details on construction]

(4) Let ON be a line tangent to M such that N is on GA and O is on GB.

(5) ∠ GMN is a right angle [See here for details]

(6) GN is greater than MN [See the corollary here for details]

(7) MN ≅ AN since:

(a) ∠ EAN ≅ ∠ EMN since they are both right angles.

(b) AE,ME are both radii, so we have AE ≅ ME and therefore (see Theorem 1, here), ∠ EAP ≅ ∠ EMP

(c) Using subtraction of step #7b from step #7a gives us ∠ NAM ≅ ∠ NMA.

(d) And #7c gives us AN ≅ MN since congruent angles implies congruent sides (see Corollary to Theorem 1, here)

(8) So GN is greater than AN too

(9) triangle AMN and triangle GMN have the same height since they are both on the same base AG and since they share the same vertice at M.

(10) Now, we can conclude that area of GMN is greater than the area of AMN since they share the same height (step #9) but the base of GMN is greater than the base of AMN (step #8) since area = (1/2)base * height (See Lemma 2 here for details if needed)

(11) triangle GLA ≅ triangle GLB by Side-Angle-Side since:

(a) GB ≅ GA since they are the sides of the same square.

(b) ∠ BGL ≅ ∠ AGL since we can prove triangle GAE ≅ triangle GBE by Side-Side-Side.

(c) Both triangles share the same side at GL.

(12) So the area of OGN is greater than half the area of BGA.

(13) The argument in step #11 applies to each side and we can conclude that converting this polygon from a 4-sided to 8-sided regular polygon results in removing greater than (1/2) the difference between the area of the 4-sided polygon and the area of the circle.

(14) We can use the same method to divide an 8-sided polygon to a 16-sided polygon and so on.

QED


References

7 comments :

Anonymous said...

This is tough. Good job man.

Anonymous said...

U rule

Anonymous said...

Larry Freeman is cool!

Anonymous said...

Hi Larry..thanks for the great page.

I noticed a mistype on Method of exhaustion, step 5 in proof of Lemma 2. The first triangle reference you have is mistyped.

Thought you might want to know so you can make a great page better.

Thanks for putting the material up.

Rich

Becky said...

Hi Larry, this is all great! I am doing the Method of Exhaustion for a final college paper and am finding your blog extremely helpful.

I do have two questions though -
In the Theorem, what are you removing 'a quantity v' from??
And then, what is the conclusion?? So you find y is greater than [(1/2)^n]*m, a value smaller than y as you promised. What does this prove??

If you get this, please feel free to email me back! Thanks a lot!
Becky

Larry Freeman said...

Hi Becky,

Thanks for your question.

As far as Question #1, we are removing a quantity v from x.

[I've updated the text in the proof to make this point clearer].

As far as Question #2, the conclusion is that we can use this insight to make proofs about relationships between circles and squares.

In Lemma 1, I show how the method of exhaustion is used to prove that when a square is inscribed in a circle, its area is greater than half the area of the circle.

-Larry

kwenger said...

Thanks for the details. I learned about the proof with the circle and polygons in class, but many of the detail were left out.
It seems the proof of the method by exhaustion would be clearer if you used symbols instead of the words "less than" or "greater than." Did you do use words for historical reasons?