Back to the Table of Contents

# Indirect and Algebraic Proofs

#### Lesson Overview

Much of the material in this chapter is a review of prior material, largely due to the fact that we started the year in the Numbers booklet. Nonetheless, it is somewhat reviewed and summarized here.

### Direct Proofs

In direct proofs, one builds on a true statement with other statements that have already been proven true. This is the typical format of a two column proof. This method includes the Law of Detachment (modus ponens) which states that if p ==> q is true and p is true, then we can conclude that q is true. Direct proofs also often use the Law of Transitivity also known as the Transitive Property of Implication. This law states that if a ==> b and b ==> c, then a ==> c.

### Indirect Proofs

Indirect proofs use negation. Negation means to take the opposite or to falsify a true statement. If the statement is p, then the negation is ~p (not p). There are many ways to rearrange and/or negate parts of statements, so we will summarize them again here. The converse of statement p ==> q is q ==> p. The inverse of statement p ==> q is ~p ==> ~q. The contrapositive of statement p ==> q is ~q ==> ~p. Converses and inverses can not be assumed true if the conditional is, a common mistake. However, the validity of the contrapositive is the same as the original—they are tautologies. That is, p ==> q is true if and only if (iff) ~q ==> ~p is true. This is known as the Law of Contrapositive. Since the converse of the inverse is the contrapositive, the converse and the inverse also have the same truth value. In addition to the Law of Contrapositive, indirect proofs often use two other common laws of logic: the Law of Ruling out Possibilities, and the Law of Indirect Reasoning (Modus Tollens).

The Law of Ruling out Possibilities is emphasized in this chapter. It is used to eliminate each possibility one by one. The Who Owns the Zebra Puzzle is typical. This and other examples are available for extra credit. Formally it states: When p or q is true and q is not true, then p must be true.

The Law of Indirect Reasoning is perhaps better known when used in proof by contradiction. Here we note that something must be either true or false. We then assume the opposite of what we suspect to be the case. We then show that this leads to a contradiction. This shows that our assumption was not valid. These proofs often do not lend themselves to a two column format. However, it is important to make the structure and method of the proof clear. Thus these proofs should start with Suppose, Assume, or Either, continues until nonsense is obtain, which should be clearly labeled a contradiction, and close with a concluding remark regarding the validity of what we intended to prove.

We used this method to show that there are an infinite number of primes. The law formally states: If valid reasoning from p leads to a false conclusion, then p is false. We thus prove p to be true by assuming first it is false and showing this cannot be.

### DeMorgan's Laws

DeMorgan's Laws show how the negation operations distributes over the and and or operations. It tends to be counterintuitive for many. Interestingly enough, in boolean algebra, multiplication and addition both distribute over each other. Remember that in boolean algebra, multiplication might be intersection or the and operator, whereas addition might be union or the or operator. Thus various symbols might be used. So not only a(b + c) = ab + ac, but also a + (bc) = (a + b)(a + c).

~(p v q) = ~p ^ ~q           [The negation of (p or q) is a tautology of (not p and not q).]

~(p ^ q) = ~p v ~q           [The negation of (p and q) is a tautology of (not p or not q).]

This is perhaps best demonstrated via a truth table.

### Algebraic Proofs

Other proofs may be algebraic or combine algebra and geometry on the cartesian coordinate plane. Certain methods and facts are indispensible. First, you must be able to find the slope of a line or between two points. Next, you need to be able to tell whether two lines are parallel (have equal slopes) or perpendicular (slopes are negative reciprocal of each other, that is, their product is -1). In addition, the distance formula is indispensible. The distance formula and Pythagorean Theorem are equivalent.

When doing a coordinate proof, the figure is often drawn in a convenient location. The origin is often utilized for one vertex, with others located on the x-axis or y-axis. Symmetry is also exploited. Thus a rectangle might be located with vertices: (0,0); (a,0); (a,b); and (0,b), or (±ab). The last expression is considered ambiguous, but we mean all four possibilities here not just two. From the coordinates, one then determines lengths and angles.

Distance can be used to show that segments are congruent. Notice how the squaring makes it irrelevant which point is considered point 1 and which is considered point 2. Distance is also always considered to be a positive quantity. The distance formula also extends to three [or more] dimensions. However, the exponents remain 2 not 3 [or more].

 D = sqrt[(x1 - x2)2 + (y1 - y2)2] D = sqrt[(x1 - x2)2 + (y1 - y2)2 + (z1 - z2)2]

The distance formula can be used to define circle and sphere algebraically.

 circle:             (x - h)2 + (y - k)2 = r2 sphere:     (x - h)2 + (y - k)2 + (z - l)2 = r2

where (h,k) and (h,k,l) are the center and r is the radius. We will generalize the circle formula next year for other conic sections (quadratic relations) such as ellipses, parabolas, and hyperbolas. Remember also, that a lattice point is a point with integer coordinates. The twelve lattice points on the circle x2 + y2 = 25 are common on contests (and in problem 11.7#14).

We find the midpoint of a line segment with endpoints (x1, y1) and (x2, y2) similarly: ([x1 + x2]/2, [y1 + y2]/2). This also trivially extends into three (or more) dimensions: a line segment with endpoints (x1, y1, z1) and (x2, y2, z2) has midpoint: ([x1 + x2]/2, [y1 + y2]/2, [z1 + z2]/2).

This, of course, is the arithmetic mean or average. We will deal with geometric mean later. Try proving this next theorem using a triangle located at (0,0); (a,0); and (b,c).

 Midpoint Connector Theorem: The segment that connects the midpoints of two sides of the triangle is parallel to the third side and half its length.

Notice how the equation of a line in two dimensions is given by ax + by = c. Similarly, the equation of a plane in three dimensions is given by ax + by + cz = d. Can you predict the equation of a 3-D space in four dimensions?

In two dimensions it is standard to graph the x-axis as increasing to the right and the y-axis as increasing upwards. Only occasionally will it differ with an axis reversed, the axes exchanged, or both. A rotation and/or reflection might be required to correct this.

The situation is far more complicated in three dimensions. Portraying three dimensions on paper is the first challenge. Many prefer to leave the x- and y-axis as is and add the z-axis at a 45° angle down through quadrant III signifying that it is coming out of the paper. Another common scheme puts the y-axis to the right, the z-axis up, and the x-axis coming out of the paper, again represented at an angle down through quadrant III. (I should note that it is common practice to shorten the scale on this axis by the square root of 2.) It is very important to label your axes, especially in three dimensions. Both of these representations obey a common convention called the right-hand rule or right-hand coordinate system. If you point your right fingers in the direction of +x, and curl them toward +y, your thumb points in the direction of +z. This important convention is embodied in the way many of our laws of physics are stated.

Additional vocabulary words: interpolation, extrapolation, incommeasurate, space (skew) quadrilateral

Example: Consider packaging constraints imposed by some shippers, specifically, maximum length plus girth is 108", where girth is the perimeter of a cross section. Assuming a square cross section, what is the maximum volume allowed.
Solution: Let 4x + y = 108 and V = x2y. Solve for y in terms of x, substitute into the volume equation, take the derivative (V = 108x2 - 4x3, V' = 216x - 12x2 = 12x(18 - x) = 0), set it equal to zero and solve for x (x=18; oops, that's calculus). Instead, graph that volume equation V=x2(108-4x) on the inverval 0 < x < 27 and 0 < y < 12000 and locate the maximum of 11664 in3 at 18" by 18" by 36" using the 2nd calc feature of your graphing calculator.

Some useful mental math (and a tie in with algebra) comes up in this section, that is the rapid squaring of x+½, for example 8.52. Note how (x+½)2=x2+x+¼= x(x+1)+¼. Thus 8.52=8•9+0.25=72.25.

See also Verignon's Theorem: If the midpoints of consecutive sides of any quadrilateral are connected, then the resulting quadrilateral is a parallelogram.

### Mathematical Induction

Mathematical induction is an important type of proof usually not covered in geometry. However, it is needed to extend some of the field axioms, such as associativity and transitivity. which we have already used. Since many texts confuse it with proof by contradiction, we include it here for completeness. The process harks back to the Peano Axiom first introduced in Numbers Lesson 2 to generate the natural numbers. Axiom 5 there is known as the induction axiom.

 A subset of N which contains 1, and which contains n+1 whenever it contains n, must equal N.

The basic flow of an induction proof is as follows. First we demonstrate our statement to be true for n = 1. Next we demonstrate that if our statement is true for any n, then it is true for n + 1. Finally, we invoke Axiom 5 above and claim it is true for all n.

Example: Suppose we want a general formula to add up all the natural numbers from 1 to n. We gave a formula back in Numbers Lesson 2, but we didn't prove it, especially for odd n.
Solution: First we demonstrate our formula Tn=n(n+1)/2 to be true for n=1. T1=1(1+1)/2=2/2=1 is the correct sum. Now assuming Tn=n(n+1)/2 is true for n we see what happens when we add n+1 to it. Tn+n+1=n(n+1)/2+n+1= n(n+1)/2+2(n+1)/2= (n(n+1)+2(n+1))/2= (n+1)(n+2)/2=Tn+1 We see that when we add n+1 to Tn we obtain the equivalent equation for Tn+1. Since the statement is true for n=1, and we have show that if it is true for Tn it is true for Tn+1, by the induction axiom, we have just proved it true for all n.

With this method it is fairly straightforward to derive formulae for the sum of squares and cubes as well. We will leave the associated algebra as homework. These will be useful in calculus when we take the limit of Riemann Sums to form integrals to find the area under curves.

The sum of i2 from i=1 to i=n is n(n+1)(2n+1)/6.

The sum of i3 from i=1 to i=n is (n(n+1)/2)2 = n2(n+1)2/4.

### Textbook Correction

Correction for textbook problem 11.5#19: 1 bushel = 1.2445 feet3 or about 1¼ feet3.

Thus BOB is wrong! Also, regarding that same problem, they seem to assume you fill the dome as well as the cylindrical part of the silo. You can go ahead and fill the dome portion today, but since silage settles so much, it won't be full tomorrow!