
Examples of Proofs 



Direct Proofs
Regular Solids
© Copyright 1998, Jim Loy 
Regular solids (regular polyhedra, or Platonic solids which were described by Plato) are solid geometric figures, with identical regular polygons (such as squares) as their faces, and with the same number of faces meeting at every corner (vertex).
If each corner consisted of two squares, then we end up with a solid made up of two squares, back to back. That's not an interesting solid. So it is not legal, as a regular solid. This eliminates the infinite number of regular polygons (triangle, square, pentagon, ...) back to back. These cannot form regular solids. So, we deduce that each vertex must have at least three faces.
If each corner consisted of four squares, we cannot enclose a space. The object that we do get is a plane, covered with squares. We say that squares can tile the plane. So we cannot produce a regular solid with four squares at each vertex. If the angles at our vertex add up to 360°, then we tile the plane, and cannot have a regular solid.
If we try to add a fifth square, we find that we have no room for our fifth square. We would have to deform our squares. And then they would cease to be squares. So, if the angles of the vertex add up to more than 360°, then we cannot fit these polygons into one corner, and we get no regular solid.
So, 360° is the upper limit on the sum of the angles at a vertex. And, we cannot have fewer than three faces at a vertex. So, there are a limited number of regular solids: 


The equilateral triangle is the simplest regular polygon. Let's start with three equilateral triangles at a vertex (total angle 180°). And we get a tetrahedron (4 faces, 4 vertices). 

We next try four equilateral triangles at each vertex (total angle 240°). And we get an octahedron (8 faces, 6 vertices). 

Now we try five equilateral triangles at each vertex (300°) We end up with an icosahedron (20 faces and 12 vertices). A sixth equilateral triangle (at a vertex) will tile the plane (360°). 

So, we try the second simplest regular polygon, the square. Three squares at each corner (270°) forms a cube, or hexahedron (6 faces and 8 vertices). And a fourth square tiles the plane (360°), as we saw with six triangles. 

The next simplest regular polygon is the regular pentagon. Three pentagons at each vertex (324°) produces a dodecahedron (12 faces and 20 vertices). Three regular hexagons, at each vertex, tile the plane (360°). And there is no room, at a vertex, for more complicated regular polygons. 


So, there are only five regular solids: 


solid 
faces 
vertices 
edges 
1 
tetrahedron 
4 
4 
6 
2 
octahedron 
8 
6 
12 
3 
icosahedron 
20 
12 
30 
4 
cube (hexahedron) 
6 
8 
12 
5 
dodecahedron 
12 
20 
30 


As you can see, there is a kind of symmetry between pairs of regular solids. And they follow Euler's formula for general convex (not necessarily regular) polyhedra (solids): faces + vertices=edges + 2. It works for some nonconvex polyhedra, and does not work for others (those with holes in them or those with points coming out of faces. 
The Pythagorean Theorem 
© Copyright 1997, Jim Loy

The Pythagorean Theorem states:
In a right triangle, with sides (legs) a and b, and hypotenuse c, then c²=a²+b².
A right triangle is a triangle with one right angle (an angle of 90°). Its hypotenuse is the side opposite the right angle. 
Proof #1: The simplest proof is an algebraic proof using similar triangles ABC, CBX, and ACX (in the diagram):
Since corresponding parts of similar triangles are proportional, a/x=c/a or a²=cx. And b/(cx)=c/b or b²=c²cx or c²=cx+b². Substituting a² for cx, we get c²=a²+b². Which is what we were trying to prove.
This proof is by Legendre, and was probably originally devised by an ancient Hindu mathematician. Euclid's proof is quite a bit more complicated than that. It is actually surprising that he did not come up with a proof similar to the above. But, his proof is clever, as well.
Proof #2: Here is another nice proof:
We start with a right triangle (in gold, in the diagram) with sides a, b, and c. We then build a big square, out of four copies of our triangle, as shown at the left. We end up with a square, in the middle, with sides c (we can easily show that this is a square).
We now construct a second big square, with identical triangles which are arranged as in the lower part of the diagram. This square has the same area as the square above it.
We now sum up the parts of the two big squares:
Area=2ab + c² Area=2ab + a² + b²
These two areas are equal:
2ab + c²=2ab + a² + b² c²=a² + b²

Proof #3: This diagram might look familiar. I've just drawn the squares on the sides of our right triangle. And, I've drawn a line from the right angle of the triangle, perpendicular to the hypotenuse, through the square which is on the hypotenuse. The idea is to prove that the little square (in blue) has the same area as the little rectangle (also in blue). I've named the width of this rectangle, x.
Using similar triangles, within our right triangle:
a/c=x/a x=a²/c
The area of the blue rectangle is xc. So we just plug in a²/c for x:
area=(a²/c)c=a²
So, the area of the blue rectangle is equal to the area of the blue square. Similarly, the area of the other rectangle (to the left of the blue one) is equal in area of the other square (b²).
So, the total area of the big square is:
c²=a² + b²
That was actually fairly easy. I made that proof up, as I studied Euclid's proof, below. 

Proof #4: We now look at Euclid's proof. Although he proved many of the theorems of algebra in his books, he did not have the methods of algebra (the manipulation of symbols) available to him. So, we must add a few more lines. We label a few points (see the diagram), and draw lines BI and CE.
Triangle ACE is congruent to triangle AIB, by the sideangleside theorem (it's a postulate, nowadays), because AC=AI, AE=AB and angle CAE=angle IAB (both angles are congruent to angle CAB + a right angle). [Note: I am using the=sign for congruence. And I am labeling a line segment as AC, because I lack more appropriate symbols].
But, the area of triangle AIB is equal to half the area of square ACHI (They have the same base AI and height IH), and the area of triangle ACE is equal to half the area of the rectangle AGFE. So, the square ACHI is equal, in area, to the rectangle AGFE. Likewise, we show that the area of the smaller square is equal to the area of the smaller rectangle.
So, the area of the large square is equal to the sums of the areas of the two smaller squares. So, we've proved the Pythagorean theorem, again. 
Here is a square with two diagonals. The area of the four triangles is 2a². The area of the square is c². Obviously a²+a²=c², a special case of the Pythagorean Theorem. If a is 1, then c is sqrt(2) [the square root of 2]. Or if c is 1, then a is sqrt(2)/2. This diagram does not seem to help in proving the Pythagorean Theorem. 
Proof by Contradiction
Irrational Numbers
© Copyright 1998, Jim Loy 
sqrt(2) = m/n (a fraction, reduced to its lowest terms)
2 = m²/n²
m² = 2n² (So, m is a multiple of 2, call it 2q)
4q² = 2n²
2q² = n² (So, n is a multiple of 2)
So, both m and n are multiples of two, which is impossible, because m/n was reduced to its lowest terms. So, we have proved that the square root of two cannot be expressed as a fraction, i.e. it is irrational.
Congruence Of Triangles, Part II
© Copyright 1999, Jim Loy
This is a continuation of the article Congruence Of Triangles. Read that article first. In that part, I stated, "All three of these congruence postulates are equivalent. You can assume any one of them, and prove the other two from there." Someone named Jason phoned me to ask how to do that. So, here is how I do it. It can be done with three proofs. But, the way I do it is with four proofs. See that article (Congruence Of Triangles), for the definitions of SAS, ASA, and SSS, as well as "congruence."
1. Assume SAS and prove ASA.
We have two triangles, as shown in the diagram. Angle A=angle EDF, angle B=angle E, and AB=DE (Note that I am using=to mean "congruent"). Prove that the two triangles are congruent.

If BC=EF, then the two triangles are congruent, by SAS. So, assume that BC not=EF.

There is a point G, on EF (perhaps extended), on the same side of the line DE, so that EG=BC.

Triangle ABC=triangle DEG [by SAS].

Angle EDF=angle EDG [definition of congruent triangles].

So DF and DG are the same line.

DF and EF intersect at both F and G. So, F & G are the same point [two distinct lines intersect in only one point].

So EF=EG=BC, which contradicts our assumption that BC not=EF.

So BC=EF, and the triangles are congruent by SAS, as mentioned in step #1.
2. Assume ASA and prove SAS.

We have two triangles, as shown in the diagram. Angle A=angle D, AB=DE, and AC=DF. Prove that the two triangles are congruent.
 If angle B=angle DEF, then the two triangles are congruent, by ASA. So, assume that angle B not=angle DEF.
 Draw a line EG, so that angle DEG=angle B (with G on the same side of DE as F).
 EG intersects line DEF (perhaps extended) at some point H.
 Triangle ABC=triangle DEG [ASA].
 AC=DH [definition of congruent triangles].
 DH=DF [both=AC]
 H and F are the saem point. And EH and EF are the same line. And angle DEG and angle DEF are the same angle.
 That contradicts our assumption that angle B not=angle DEF.
 So angle B=angle DEF, and the 2 triangles are congruent by ASA, as mentioned in step #1

3. Assume SSS and prove SAS.

We have two triangles, as shown in the diagram. Angle A=angle EDF, AB=DE, and AC=DF. Prove that the two triangles are congruent.

If BC=EF, then the two triangles are congruent, by SSS. So, assume that BC not=EF.

Find the point G (on the same side of line DE as F is) so that DF=DG and BC=EG. We do this by drawing arcs of those radii and finding where they intersect, if they do intersect.

Triangle ABC=triangle DEG [SSS].

Angle A=angle EDG [definition of congruence of triangles].

Angle EDG=angle EDF [both=angle A].

So, they are the same angle. And F and G are the same point. And EF=BC.

This contradicts our assumption that BC not=EF.

So BC=EF, and the triangles are congruent by SSS, as mentioned in step #1

4. Assume SAS and prove SSS.

We have two triangles, as shown in the diagram. AB=DE, AC=DF, and BC=EF. Prove that the two triangles are congruent.

If angle A=angle EDF, then the two triangles are congruent, by SAS. So, assume that angle A not=angle EDF.

Draw a line DG, so that angle BAC=angle EDG.

Find the point H (on the same side of DE that F is) so that DH=AC.

F & H are not the same point [DF and DG can only intersect at D].

Draw EH and FH.

Triangle ABC=triangle DEH [SAS].

EH=BC [definition of congruent triangles].

EH=EF [both=BC].

DH=DF [both=AC].

Both triangle DFH and triangle EFH are isosceles [definition].

The perpendicular bisector of FH must pass through both D and E [a Euclid theorem, which I will track down later].

So DE is the perpendicular bisector of FH [definition].

But that is impossible, since H and F are on the same side of line DE [step #3].

This contradicts our assumption that angle A not=angle EDF.

So angle A=angle EDF, and the triangles are congruent by SAS, as mentioned in step #1.


Mathematical Induction
Dividing the Plane
© Copyright 1997, Jim Loy 

A line divides the plane into two pieces (regions). Draw another line. The plane is now divided into three or four regions. It is three regions if the lines are parallel, four if they intersect. For the purposes of this article, we want the greatest number of regions. So, two lines, four regions. A third line divides the plane into seven regions (See the diagram). The results, so far:
Lines 
Regions 
1 
2 
2 
4 
3 
7 
Using a little algebra, we can find an equation for the first three lines:
R(n) = an² + bn + c
2 = a + b + c
4 = 4a + 2b + c
7 = 9a + 3b + c
...
R(n) = (n²+n+2)/2
We see, from the diagram, that four lines produces eleven regions. So we see that our formula works for four lines. And we suspect that it is valid in general. How do we prove that?
Let's say that we've got n lines (for some arbitrary n). And we add an n+1th line. That line goes through regionlineregionline...lineregion. It went through n lines and n+1 regions (assuming that all of the lines intersect). For each region that it went through, it added a region (split that region into two regions). So it added n+1 regions. So, we've just proved the rule: R(n+1)=R(n) + n + 1.
Our earlier formula, which works for some n, is:
R(n) = (n²+n+2)/2
What is R(n+1), by that formula?
R(n+1) = [(n+1)² + (n+1) + 2]/2
= (n²+3n+4)/2
= (n²+n+2)/2 + n + 1
In other words:
R(n+1) = R(n) + n + 1
So, our formula follows the rule R(n+1)=R(n) + n + 1. This means that we have actually proved our formula, by Mathematical Induction. Our formula works for the first case (n=1). And we showed that if the formula works for some n, then it works for n+1.
By using Mathematical Induction, we have shown that if our formula works for n=1 (which it does), then it works for n=2. And if it works for n=2, then it works for n=3. And if it works for n=3, then it works for n=4, etc. In other words, it works for all, infinitely many cases, from 1 on up.
Our formula, R(n)=(n²+n+2)/2 is an integer divided by 2. Does it always give us an integer for R(n)? It should, because we never end up with a fraction of a region. Well, if n is even, then n² is even and n²+n+2 is even, we get an integer when we divide by 2. If n is odd, then n² is odd and n²+n+2 is even, we get an integer when we divide by 2.
Incidentally, our formula works for n=0. With no lines, we find that the plane is divided into one region. In our proof, we could have saved a little effort, by using n=0 as the first case. 

Proof by Contrapositive
Examples 
Parity
Here is a simple example that illustrates the method. The proof will use the following definitions.
Definitions.
 An integer x is called even (respectively odd) if there is another integer k for which x = 2k (respectively 2k+1).
 Two integers are said to have the same parity if they are both odd or both even.
For the purpose of this example we will assume as proved that each integer is either even or odd.
Theorem. If x and y are two integers for which x+y is even, then x and y have the same parity.
Proof. The contrapositive version of this theorem is "If x and y are two integers with opposite parity, then their sum must be odd." So we assume x and y have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose x is even and y is odd. Thus, there are integers k and m for which x = 2k and y = 2m+1. Now then, we compute the sum x+y = 2k + 2m + 1 = 2(k+m) + 1, which is an odd integer by definition.
How Is This Different From Proof by Contradiction?
The difference between the Contrapositive method and the Contradiction method is subtle. Let's examine how the two methods work when trying to prove "If P, Then Q".
 Method of Contradiction: Assume P and Not Q and prove some sort of contradiction.
 Method of Contrapositive: Assume Not Q and prove Not P.
The method of Contrapositive has the advantage that your goal is clear: Prove Not P. In the method of Contradiction, your goal is to prove a contradiction, but it is not always clear what the contradiction is going to be at the start.
A Test For Perfect Squares
In this example, we will need two notions. An integer n is called a perfect square if there is another integer k such that n = k2. For example, 13689 is a perfect square since 13689 = 1172.
The second idea is the remainder and modular arithmetic. For two integers m and n, n mod(m) = r will be the remainder resulting when we divide m into n. This means that there is an integer q such that n = mq + r. For example, 127 mod(29) = 11 since 29 will go into 127 4 times with a remainder of 11 (or, in other words, 127 = (4)(29) + 11). Determining whether or not a positve integer is a perfect square might be difficult. For example, is 82,642,834,671 a perfect square? First we compute 82,642,834,671 mod(4) = 3. Then use this theorem:
Theorem. If n is a positive integer such that n mod(4) is 2 or 3, then n is not a perfect square.
Proof. We will prove the contrapositive version: "If n is a perfect square then n mod(4) must be 0 or 1." (Do you understand why this is the contrapositive version?) Suppose n = k2. There are four cases to consider.
 If k mod(4) = 0, then k = 4q, for some integer q. Then, n = k2 = 16 q2 = 4(4 q2) , i.e. n mod(4) = 0.
 If k mod(4) = 1, then k = 4q + 1, for some integer q. Then, n = k2 = 16 q2 + 8 q + 1= 4(4 q2 + 2 q) + 1, i.e. n mod(4) = 1.
 If k mod(4) = 2, then k = 4q + 2, for some integer q. Then, n = k2 = 16 q2 + 16 q + 4 = 4(4 q2 + 4 q + 1), i.e. n mod(4) = 0.
 If k mod(4) = 3, then k = 4q + 3, for some integer q. Then, n = k2 = 16 q2 + 24 q + 9 = 4(4 q2 + 6 q + 2) + 1, i.e. n mod(4) = 1.
