Proof Tutorial 1: Introduction to Mathematical Proofs

Introduction

Routine problems in mathematics usually require one or many answers . If we are asked to find the smallest of the three consecutive integers whose sum is 18, then our answer would be 5. If we are asked to find the equation of a line passing through (2,3), we can have many answers.

Proofs, however, is different. It requires us to think more and to reason with valid arguments. It requires us to be explicit and logical. It requires us to convince our readers and most of all ourselves.

Unless a proof problem is already given, finding mathematical statements to prove requires us to see patterns, generalize, and make conjectures about them. The problem stated above about consecutive integers does not require us to reason much or generalize at all.

The success of proof writing requires intuition, mathematical maturity, and experience. Contrary to mathematical proofs written in books, the ideas behind arriving at a proof are not “cut and dried” and elegant.  Mathematicians do not reveal the process they go through, or the ideas behind their proofs. This is also a skill that mathematicians and persons who are good in mathematics possess: they are able to read proofs. The skills of reading proofs may be achieved by learning how to write them.

 

Proving in higher mathematics, on the other hand, requires formal training. For instance, we have to know how to use logical connectives like and, or, not, and must understand how conditional and biconditional connectives work. Basic set theory concepts are also important. Moreover, we also have to learn proof strategies like direct proof and proof by contradiction to name some.

For now, we will not be discussing these things . Most of the proofs in basic mathematics only require a little intuition and good reasoning.

In the tutorial below, I tried to recreate (amateurishly) the process on how mathematicians see patterns, arrive at a conjecture, and how they prove their conjectures.  Of course, in reality, problems mathematicians encounter are a lot harder. In fact, some of the hardest problems take hundreds of years to be solved. For example, no mathematician has proved the Fermat’s Last Theorem for more than 300 years, and the mathematician who proved it solved it for eight years.

The proof that we are about to do below is very elementary. For now, we will highlight the process and not the difficulty. The titles of the processes below are not necessarily in order.

Recognizing Patterns and Making Conjectures

Before mathematicians prove theorems, they usually first see patterns. This happens when they read books, solve problems, or prove other theorems. For example, what do we see when we add two even integers? Let’s add some: 2 + 8 = 10, – 24 + 6 = -18, and – 4 + – 8 = -12. We can easily see that if we add two even integers, then their sum is always even.

From here, we might be tempted to say that if we add two integers, then their sum would always be even.  In mathematics, this kind of statement or hypothesis is called a conjecture: an educated and reasonable guess based on patterns observed. Rewriting our guess, we have

Conjecture: The sum of two even integers is always even.

If we want to disprove a conjecture, we only need one counterexample — an example that can make the conjecture false. (Can you think of one?). Note that  we only need one counterexample to disprove a conjecture.  If we want to prove it, however, we might be tempted to pair a few more integers and say that “oh, their sum is even, so it must be true”. No matter how many integers we pair, if we can’t exhaust all the pairs, then it cannot be considered as a proof.  When we say the sum of two even integers above, we mean ALL even integers.  Of course, there is no way that we can list all pairs of even integers since there are infinitely many of them.

Generalizing Patterns

Since it is impossible to enumerate all pairs of even integers, we need a representation, algebraic expression in particular, that will represent any even integer. If we can find this expression, then all the even integers would be represented. This process is called generalizing.  Like what we have done above, we generalized by representing all members of the set by a single expression. In our case, the members of our set are all even integers.

 

From the definition, we know that all even integers are divisible by 2. That means that if m is an even integer, then, when we divide m by 2, we can find a quotient which is also an integer. For instance, since 18 is an integer, we are sure that there exists an integer such that 18 divided by 2 is equal to that integer.

In general, suppose that quotient of m/2 is q, then it follows that m/2 = q, for any even integer m. Multiplying both sides of the equation by 2, we have m = 2q. That means that if m is an even integer, then there exists an integer q such that m = 2q. Hence, we may represent any even integer m with 2q for some integer q*. Note that q here is a generalized number, which means that an even integer can also be represented by 2x, 2y, 2z or any variable with the condition that they are integers.

Connecting the ideas

Proving is making logical and relevant statements from definitions, facts, assumptions and other theorems to come to a desired conclusion. Before coming up with an elegant proof, mathematicians usually have scratch work, connecting their ideas to arrive at what they want to prove.

Scratch work

From the statement above, we have shown that any even integer m, there exists an integer q, such that m = 2q. That means, that if we can show that the sum of two even integers is in the form 2q (or that the sum is divisible by 2), then we can be sure that it is always an even integer.

Since we need two integers, we let m and n are the two integers that we will add. Since both of them are even integers, then we can represent them as 2q and 2r respectively for some integers q and r. Adding both of them, we have m + n = 2q + 2r = 2(q + r). Now, q + r is an integer since q is an integer and r is an integer from our definition above. This means that 2(q + r) isof the form 2x for some integer x. This means that m + n is of the form 2x for some integer x. Therefore, m + n is even.

Writing (elegantly) the final proof

Here, we write our proof in a shorter and more elegant way. Conjectures that are proven are called theorems. So let us write the proof of our first theorem.

Theorem 1: The sum of two even integers is always even.

Proof. Let m,  n be even integers.  Then m = 2q for some integer q and n = 2r for some integer r. Now, m + n = 2q + 2r = 2(q + r). Since q + r is an integer, clearly, 2(r + s) = m + n is divisible by 2. Therefore, the sum of two even integers is even.

Most proofs are written in a concise way, leaving some details for the reader to fill in. For example, the statement “Since q + r is an integer” did not really state the reason why this is so. This is stated in our scratch work, but not in the proof.

Going Further

If m is an even integer, then m – 1 and m + 1 are odd integers. Since m = 2r, then 2r – 1 and 2r + 1 are also odd integers. In our example below, we will use 2r + 1, to prove that the sum of two odd integers is always even. As an exercise, use 2r – 1 in your proof.

Theorem 2: The sum of two odd integers is always even.

Let p, q be odd integers. Then p = 2a + 1 and q = 2b + 1 for some integers a and b. Now, adding we have p + q = 2r + 1 + 2s + 1 = 2r + 2s + 2 = 2(r + s + 1). Since r + s + 1 is an integer, then 2(r + s + 1) is divisible by 2. Hence, p + q is divisible by 2. Therefore, the sum of two odd integers is even.

Math and Hardwork

Being good in math requires hard work. Andrew Wiles worked on the Fermat’s Last Theorem for seven years, have given up several times thinking that it was impossible. In 1995, he finally thought he had proved it, and presented it in a conference.  A month later, his reviewer thought that there is a part of the proof which was vague (or wrong), so he had to review his work and found out that there was a part which was actually wrong.  He almost gave up. He worked more than a year to correct the error.

Now, he has carved his place in history.

*In technical language, the word “for some” is equivalent to the word “there exists”.

Exercises:

  1. Prove that the sum of an even number and an odd number is always odd.
  2. Prove that the difference of two odd integers is always even.
  3. Prove that the product of two even integers is always even.
  4. Prove that the product of two odd integers is always odd.
  5. Prove that the product of an even number and an odd number is always even.

Leave a Reply