PROOFS

Conclusions can be reached by authority, guessing, revelation, trial and error, etc. In mathematics, there usually are two procedures describing how conclusions can be reached. One is inductive reasoning and the other is deductive reasoning. (To actually prove a statement in math and accept the conclusion requires proof by deductive reasoning.)

Inductive reasoning occurs by finding a pattern and assuming the pattern holds even where it is not yet checked. Conclusions may or may not be valid (correct). Inductive reasoning usually is described as two types – inductive and analogy. These will be described below.

Deductive reasoning requires procedures of logic that are generally accepted and, therefore, lead us to valid conclusions. Deductive reasoning has many different approaches, nine of which will be described following the sections on inductive reasoning and analogy.

Inductive Reasoning

There are many events in which we observe a common pattern. When we observe the pattern in some of the events but do not check all the events, we conclude that the pattern in valid for all the events.
 ..... Example:      We wish to enter the technology building and find the door next to the admissions office is locked. We try the door to the administrative offices and it is locked. We walk around to the cafeteria doors and they are locked. Therefore, without checking the rest of the doors, we conclude that all the doors are locked and we leave. ..... Example: A pendulum is made by a weight suspended by a string of a fixed length. The string remains fixed, but the length of the arc that is swept out by the weight depends upon how far the weight is pulled to one side before releasing it. We clock the time for the weight to make one swing through the arc that it makes. If we clock one swing for five different arc lengths, the time is the same (it travels faster through a longer arc). We conclude the time is always the same for a pendulum with a fixed string length, regardless of the arc length through which the weight swings. Because of this, the pendulum clock was easier to make. ..... Example: Every time we have added two integers, we get a sum that is an integer. We conclude that for any two integers we add the sum will always be an integer.

Inductive reasoning helps to make up statements which we only assume to be true (calling them axioms), or we prove them to be true by deductive reasoning. Inductive reasoning of itself does not prove a conclusion to be valid.

Analogy Reasoning

There are two situations that we have found to have many characteristics in common. We observe in one of the situations a new characteristic and conclude the other situation must have the new characteristics also.

In the first example, the characteristics were the same for the two situation (i.e., they both play basketball). The second example depends upon changes in one situation causing changes in the other situation, where measurements of one are associated with measurements of the other.

A thermometer is a cause/effect change. A 10 rise in temperature may cause a 1/25-inch rise in a thermometer tube. We don’t read the thermometer saying there is a 1/25 inch rise in temperature, rather the thermometer is marked in 0 C and we read a 10 C rise in temperature (which by analogy is associated with a 1/25 inch change). Similarly, we don’t read an auto speedometer needle as so many degrees arc length speed. There is a kpm or mph scale under the needle.

Deductive Reasoning

Deductive reasoning consists of undefined terms, definitions, axioms (unproved statements), theorems (proven statements), and a logic which enables us to prove the theorems. If we think of mathematics as numerous systems consisting of the above five parts, then math is alive and well and growing in two directions. Systems along this line are sometimes related and usually the logic used to prove the theorems is logic accepted by most mathematicians! Many difficulties arise in math since we learn math that is around the middle of this line, not knowing all the axioms or all the theorems available that have been proven – nor even the undefined terms and definitions. From somewhere along this line, we prove statements (theorems).

If one of these systems is fairly well developed, we may assign meanings to the undefined terms in the system in such a way that the axioms make sense to us and the result is an applied mathematical system. Different applied systems or sciences result for different meanings assigned. Math is not concerned with the truthfulness of the axioms, but with the validity of the proofs. In fact, the word “true” if often used loosely with a hypothesis or axiom and it really means we assume the hypothesis is true or assume the axiom is true. Also, for a proven theorem with a valid (deductive) argument, we sometimes say the conclusion is true; but we really mean we have a valid conclusion from a deductive argument.

There are many common words that are used in math in a very technical way. We will look at some of these before discussing different methods of proof. Words such as “all,” “every,” “any,” “each,” “none,” and “no” are called universal – that is, they apply to every object they are used with. “All trees have leaves” is a universal statement about each and every tree. “No trees have feathers” is also a universal statement. Words like “some” or “at least one” describe the existence of at least one of the objects discussed. “Some people are reading this paragraph” is an existential statement that happens to be true if we can find one or more people reading this paragraph.

If there are four people in a room and we say, “Some people in the room are seated;” it is true if we find at least one seated person. There may be one, two, three, or all four seated, but that doesn’t concern us as long as we find at least one. By interpreting “some” this way, the negation of an existential statement will be a universal statement (to be explained further in the next paragraph). Also, the negation of a universal statement will be an existential statement. The negation of the negation of a statement will be itself!

Therefore, if four people are in a room, there are five possibilities or cases: zero seated, one seated, two seated, three seated, or four seated. Statements describing these cases are given below using none and some, then using some and all. Relations of the negations of these statements (A, B, C, & D) are as follows: (Use of the word “some” in every day English often means, “if some do, then some don’t”. In math, “some do” only means one or more do. This meaning preserves the logical statements above.)

There are two additional words in math that have a technical meaning – “and” and “or.” The word “and” in normal use of the English language is usually the same as in math. In math, though, if you have a combined statement – “A and B” – then the statement “A” and the statement “B” should make sense when stated alone. Also, it is not necessary for there to be a logical relation between “A” and “B” (though there usually is). Therefore, it follows by logic used in math that if statement “A” is a true statement and if statement “B” is a true statement, then the combination “A and B” has to also be true regardless of any relationship between “A” and “B.” Likewise, if combined “A and B” is a true statement, then “A” alone is a true statement and “B” alone is a true statement.

The word “or,” when used in math, has the same meaning as “and/or.” “A or B is true” means that “A” is true or “B” is true or both “A” and “B” are true. (The word “or” in every day English normally excludes this last possibility – that “A” and “B” could both be true. But in most math systems, it is included.) “I had tomatoes and eggs for breakfast,” mathematically means one of the three possible repasts: eggs only, tomatoes only, or both eggs and tomatoes.

Deductive reasoning is mathematical proof. All methods or approaches used in proofs are derived from the direct method of proof that will be described below. Other names used in describing methods or approaches are just that - names of convenience describing methods of proof that basically arise from the direct method. The methods are so different that we categorize them by different names for convenience in attacking problems. The following methods or approaches will be discussed: Direct Method of Proof

The direct method of proof brings together statements such as axioms, proven theorems and definitions and proves a new statement. A reason is often given with each step of the proof. Some steps in the proof are left out if they are believed to be obvious at the level of the ability of the reader.

 ..... As with most proofs, some steps are left out and, sometimes, unnecessary steps at some readers’ levels are included. The reason above that the products of the left sides are equal to the product of the right sides or two equations is sometimes given as an axiom. If a, b, c, and d are real numbers and if a = b and c = d, then ac = bd. Sometimes, this is proven as a theorem from other axioms. (After one understands its use, it is usually left out of proofs completely.) A shorter version of this proof would be: ..... Here again, a lot of steps are left out; otherwise, it would take too long to go very far in math. There are enough steps above with sufficient reasons to be quite convincing. Blatantly, the picture represents much assumed information. It could have been constructed by starting with one triangle, constructing a square of side c, constructing the next triangle which would have corresponding angles equal to the first, but side c would be equal in length making them congruent, etc. Or one could begin with the larger square and construct the triangles inside it, etc. To be an “obviously” correct picture assumes some knowledge of statements in geometry and of what pictures in geometry represent.
 The Indian philosopher, Bhaskara, gave his proof of the Pythagorean theorem as the pictures on the right with only one word of explanation. The basic idea, though, for the direct method is seen in the examples above (i.e., an hypothesis (assumptions) and a valid argument with sufficient reasons to reach a conclusion). If the hypothesis is assumed to be true and the argument is valid, then the conclusion is inescapable!

Replacement and substitution are used repeatedly in math proofs, though rarely given as reasons.
 Example for replacement: xn xm = xn+m Replace x with a and we have: an am = an+m Or replace x with 5 and we have: 5n 5m = 5n+m

 Example for substitution: xn x -m = xn x -m x -m = 1 / xm Definition of negative exponents xn / xm = xn x -m Substitution of 1 / xm for x -m in left side of first equation

Substitution allows us to exchange any statement, S, in a formula with an equivalent statement. It is not necessary to exchange every statement in the formula with the equivalent statement. Replacement, on the other hand, exchanges a variable, x, in a statement for another variable or constant or formula. Every x has to be exchanged. Replacement and substitution will make changes that are valid.

Many logical arguments in math are constantly being used in proofs without mention. One of these valid implications is given below. Let the symbols P, Q, and R represent statements.

If P is assumed true and if the implication, P implies Q, is valid, then the conclusion is that Q is true. In abbreviated form: .....  These arguments probably seem quite logical. That is why they are generally accepted and also why they are not always stated as reasons in proofs.

Indirect Method of Proof

The indirect method of proof of P - > Q, (read, statement P implies statement Q), is based on the contrapositive of the implication. The contrapositive of P -> Q is ~Q -> ~P, (read, the negation of Q implies the negation of P). It is possible to show by a direct proof that an implication and its contrapositive are equivalent.

P -> Q is equivalent to ~Q -> ~P

Let’s try to intuitively see the connection. Let P = it rains, and Q = the yard is wet. Now, assume the implication is true that P -> Q, or

If it rains, then the yard is wet.

Then, it must follow that ~Q -> ~P, or

If the yard is not wet, then it didn’t rain.

For if it did rain, then P -> Q would guarantee a wet yard, which we don’t have in ~P -> ~Q!

In like manner, if we started with the assumption: ~Q -> ~P, then it would follow that P - >Q.

To say an implication and its contrapositive are equivalent merely means that if we prove one of them, then the other automatically follows. We will examine three approaches of the indirect method that we call the contrapositive, the contradiction, and cases.

Contrapositive Approach

Generally, to prove P - >Q, one starts with ~Q and uses a valid deductive argument to prove ~P. (The hypothesis, P, can not be used here as a reason in the valid argument. But, in the next approach, the contradiction approach, P can be used.) The contrapositive is the most straightforward of the indirect methods of proof approaches, but it is more useful in proving the other approaches than in actually proving theorems.
 ..... The above is a proof of the contrapositive: if n is not even, then n2 is not even. This is equivalent to the implication – if n2 is even, then n is even. (Notice the direct method of proof is used above to prove the contrapositive from ~Q to ~P. Once this is proven, then by the indirect method, we automatically have P -> Q.)
 ..... Since we have shown ~Q -> ~P, then P -> Q and the statement is proven.

An approach we call the contradiction approach will handle statements of the form A and also of the form P -> Q. By form A we mean any statement that we choose not to write in the form P -> Q as will be seen in the first example below ( is irrational).

The next two paragraphs explain the contradiction approach. This is easier to do than to explain so you may wish to skip to the summary and examples below which should be easier to follow. The first example proves a statement of the form A, and the second example proves a statement of the form P -> Q.

If we want to prove statement A, we can assume ~A and find any valid argument which takes us from ~A to a contradiction (the contradiction arises from any previous statement we have accepted). Suppose we have accepted as true a statement S from a previous Axiom or theorem. Next, we use ~A to prove ~S. Therefore, S and ~S would be a contradiction. Since S is accepted as true, then ~S is false and ~A is false. “~A is false” = ~ (~A) = A ! In other words, ~A was used to prove ~S, and the contrapositive of this would be ~ (~S) -> ~ (~A), where ~ (~A) = A .

If we want to prove an implication, P -> Q, we can assume P is true and ~Q is true and find a valid argument which leads us to a contradiction. The contradiction can be any S and ~S which includes now P and ~P, Q, and ~Q, or any other accepted S where we can also prove ~S. Notice here that the hypothesis P may be used as part of the valid argument. It also should be mentioned that if the negation of P - >Q leads to a contradiction, then the combined P and ~Q will lead to a contradiction.
 To summarize the contradiction approach: To prove A, find a valid argument from ~A to a contradiction. Therefore, ~ (~A) = A. To prove P -> Q, find a valid argument from P and ~Q to a contradiction. [~(P -> Q) is equivalent to P and ~Q. Therefore, ~(~P -> Q)) = P -> Q.]

 ..... ..... ..... Cases Approach

The third approach of the indirect method of proof for p -> Q we call the cases approach, and this approach can also be proven from the contrapositive. (This approach is almost identical to what is called the “elimination” approach in geometry.) We break ~Q into a finite number of cases, A, B, C, ..., where ~Q = A or B or C or . . . . Then we only have to prove that each case implies ~P. In other words, we prove A -> ~P,  B -> ~P,  C -> ~P, . . ., where any valid argument – direct or indirect – may be used for each case.

 To summarize the cases approach for P -> Q: Let ~Q = A or B or C or ..., and prove by any valid argument each of the cases: A -> ~P, B -> ~P, C -> ~P, ... .

 ..... Mathematical Induction (not inductive reasoning)

The term “mathematical induction” is another one of those unusual (confusing) names found in math. It may sound like, but does not mean, inductive reasoning. (To call it “valid inductive reasoning” would be contradictory!) Anyway, mathematical induction approaches are based on the axiom of finite induction. This axiom has many equivalent forms – the easiest is as follows:

 If S is any set of natural numbers, (natural numbers is another name for positive integers) and S contains the natural number 1, and if S contains the natural number k, then it also contains the natural number k + 1, then S contains all natural numbers.

Given the three parts of the hypothesis above, the conclusion is S contains all natural numbers. Intuitively, since S contains 1, we can let k = l, and k + l = 2 is in S. Now that 2 is in S, let k = 2, and k + 1 = 3 which is in S; and so forth.

Now we are talking about all natural numbers. Suppose Tarzan makes a mark or stripe, /, in the sand for the natural number 1. Then he adds another stripe, //, for the number 2; and adds another stripe, ///, for the number 3. We may run out of names for the number of stripes, but Tarzan stripes forever! Inductive reasoning leads us to accept the idea of adding / forever to obtain all natural numbers.

The axiom for finite induction is just that – an axiom (unproved statement) that most mathematicians accept. This axiom is necessary for most mathematics.

A method of proof called The Principle of Mathematical Induction follows directly from the axiom of finite induction. We will now examine this principle and three others that can be proved from the finite induction axiom:

 Principle of Mathematical Induction Approach Mathematical Induction 2 Approach Mathematical Induction 3 Approach Infinite Descent Approach

Principle of Mathematical Induction Approach

 Associate with each positive integer, n, a mathematical statement S(n). If S(1) is proven true, and if for any positive integer, k,  S(k) implies S(k + 1), then S(n) is true for all n.

 ..... To finish the proof, we need to assume S(k) by “replacing” n with k in S(n) getting 2 + 4 + 6 . . . + 2k = k(k+1), and prove that this will lead to the mathematical statement S (k + 1), replacing n with (k+1), which is 2 + 4 + 6 . . . + 2(k+1) = (k+1) [ (k+1) + 1]. We can’t use our conclusion, S(k+1), as a reason in our proof, but we can examine the conclusion in order to have a better idea of where our proof should be leading. For example, the right side of the conclusion above that we are shooting for is (k+1) [ (k+1) + 1], which equals (k+1) (k+2) or k(k+1) + 2(k+1). This is just the right side of S (k) with 2 (k + 1) added. So, let’s assume S(k) and add 2(k+1) to both sides. ..... ..... Often a proof is stopped at the end of the scratch work since it is obvious that the steps are reversible. One must be careful! If you are familiar with proving trigonometry identities, you generally work only on one side of the equation using only identities. This insures that the steps are reversible, and the proof is actually the steps in reverse.
 ..... The formula above for the sum of the first n odd natural numbers was known over 2,000 years ago – probably by adding an odd number of pebbles or dots, forming a square. ..... ..... We can let A (4) be our first term and continue on to prove A (k) ->A (k+1). (It is not necessary, but we could have actually let A (4) = S (1), and A (5) = S (2), etc.) ..... The proof above makes use of pictures. One must be careful with the use of pictures. Generally, assumptions are made from the pictures that are not stated in the proof. Again, this depends on the reader’s level (and sometimes on the writer’s level).

Mathematical Induction 2 Approach

 Associate with each positive integer, n, a mathematical statement, S(n). If S(1) is proven true, and if assuming every S(k) is true for all positive integers k < m implies S(m) is true, where m is any positive integer, then S(n) is true for all n.

 ..... This theorem is part of the proof of the Fundamental Theorem of Arithmetic (also called The Unique Prime Factorization Theorem) which states that any natural number larger than 1 is prime or can be represented as a unique product of primes if the prime factors are in order; 2,  3,  4 = 2 * 2,  5,  6 = 2 * 3,  7,  8, = 2 * 2 * 2,  9 = 3 * 3,  10 = 2 * 5,  11,  12 = 2 * 2 * 3 ,  13,  14 = 2 * 7, etc. Uniqueness is not proven in the above example.

Mathematical Induction 3 Approach

 Associate with each positive integer, n, a mathematical statement, S(n). If for a specifically identified positive integer, h, we prove S(1), S(2), and so forth through S(h), [in other words, prove S(n) for n

 ..... Before proving this, it is interesting that these Sn terms generate the sequence of values, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..., called a Fibonacci sequence after Leonado Fibonacci of the 13th century. Each term here is defined as a function of n. Each term was originally defined recursively (each term defined by the preceding terms), as the sum of the two preceding terms, 1+1 = 2, 1+2 = 3, 2+3 = 5, 3+5 = 8, 5+8 = 13, etc.

An interpretation of this sequence is rabbit breeding. Begin with one pair. Each pair of rabbits is fertile after one month. Each fertile pair gives birth to a pair each month. They all stay healthy. Then Sn is the number of rabbits after n months. \$! Some tree branches and rows of sunflower seeds increase following a Fibonacci sequence. Infinite Descent Approach

Associate with every positive integer, n, a statement, S (n). We wish to show S(n) is not true for any positive integer, n. Begin with the indirect approach by assuming there is some m such that S (m) is true and find a contradiction. We do this by proving S (m) implies S (k) is true for some positive integer k<m. Since the general form is proven S (m)->S (k), then there will be a positive integer less than k where the statement is true, and so forth forever. One can’t descend among positive integers forever since there is a lowest positive integer, the number 1. With this contradiction, S (n) is not true for any positive integers.

To summarize the infinite descent approach:

To prove S(n) is false for every positive integer, n,

assume there exist an S(m) that is true and prove it implies S(k), where k<m and k and m are positive integers.

 ..... Counterexample Method for Disproof

The Counterexample Method proves a statement to be false by finding an example where it is false. (Generally, the statement is a universal statement. To negate a universal statement requires an existential statement, which needs only one example or case showing something exists.)

It is usually easier to make a statement, S, and knock it down by finding an example that is counter to your statement. Then you have proved the statement, S, is false.
 ..... ..... Many functions have been devised in an attempt to find one that will define an infinite set of prime numbers. F (n) = n2 – n + 41 is prime for n < 41, but f(41) = 412. F(n) = n2 – 79n + 1601 is prime for n < 80, but f (80) is not a prime number. 