How I Do Proofs

This is not meant to be a complete solution to doing mathematical proofs. However this is the procedure that I actually follow when doing proofs. I am usually not consciously aware of each step, but I do them all at some level. Here is the flowchart:

Explanation of the Steps:

Read The Problem: The obvious first step.

Do I Understand It?: It is important to understand what the question is asking you to show before trying to show it.

Work It Out: This is where you try to figure out what the problem says. Now you need to go back and try to sort out all of the definitions and see how they apply. (The lists of notation at the end of each chapter, and the end of the book, are useful for finding definitions.) It also helps to talk to other people, including classmates and me. Also you can try taking a concrete example that you understand, and try to interpret what the question would say about that example. After that you may find it easier to understand the question.

How Many Parts?: How many individual parts are there to prove in the question? Be careful, innocent looking phrases like “if and only if” (often written “iff”) mean that there are two statements to prove. A more subtle example is, “There exists a unique _____” where you usually have to prove existence and uniqueness separately. Sorting this out now will help make sure that you do not skip anything lter.

Select a Part: Select one part of the problem to try. Which part does not matter (you will have to do them all eventually) but it is important that you select only one part at this time. If you accidentally try to do two, then you will find yourself getting nowhere.

Do Known Techniques Apply?: Over time you will develop a toolbox of standard methods for doing proofs. Each method is good for certain things, and usually there are key phrases that suggest whether a given method may apply. Not all methods have formal names (and the lines between different methods are not always clear), but here are some method which you hopefully will have in your personal toolbox by the end of this course:

- Directly: If you see a phrase like, “If A then B” then you try assuming that A is true and try to show that B follows as a conclusion. Other phrases that indicate that this technique is called for are “All A’s are B’s” and “A is a subset of B”. In these cases you assume that x is an element of A and proceed from there.
- Show The Contrapositive: If the direct method does not work, then try assuming that B is false, and try to show that A is false. If you can do this then you have shown that it is is impossible that A is true and B is false...which is what you wanted to show.
- Uniqueness: When you see “Prove that (X) is unique” your first thought should be, “Assume that X, X’ are two things satisfying the definition of (X)...” and try to show that X = X’.
- Induction: Hopefully you have all seen this. The idea is to prove that some statement is true about all of the positive integers by showing that it is true for 1 (the base case), and then showing that if it is true for n-1 then it is true for n (the induction step). At this point you have shown that it is true for 1, 2, 3, … ad infinitum. In other words, you have shown it for the positive integers.
- Algebraic Manipulation: This is a perfectly good form of proof! And so is a direct computation.
- Apply The Theorem: Often a problem will turn out to be a special case of, or a direct consequence of, a theorem that you know. Often that will be a theorem that you have seen recently (since we are trying to get you to understand and remember that theorem), so it may be worthwhile to try to apply the theorem and see whether you get anything useful.
- Contradiction: Assume that the result that you want is false, then try to prove something that is impossible. You will then have proven that your result cannot be false, so it must be true. This can be used in a wide variety of situations.

If you are not used to all of these yet, do not worry. We do not expect you to have mastered them at this point. Also there is one “meta-technique” that is so useful that I am giving it its own section...

Any Ideas On Why It Is True?: If you have none, then do not worry. But if you have a general, perhaps imprecise, idea on why the result makes sense, then that can give you a “game plan”. It may suggest a technique, suggest helpful examples, make later steps a matter of “filling in details”, and so on. It may also give the satisfaction of feeling that you “understand” what is “really” going on. But we cannot expect this to happen, and “plugging away” at the problem without waiting for “insight” that may or may not come will usually work.

Note that while trying to get this conceptual idea it is worthwhile to work example which might give you a sense of what is going on. Also trying to prove that the result is wrong is very helpful because when you think about why you are failing, you can get a sense of why the result may be true.

Incidentally, at this step you might come up with a “heuristic proof”, meaning a somewhat plausible (though not totally correct or complete) line of reasoning showing why the result should work. These arguments sometimes are very useful. (This is not the space to get into a discussion of how useful they are, and why.) But you need to be aware that they are not really proofs.

Try to Find a New Technique: At this point your toolbox needs to get larger. There are no set techniques here, but there are some general guidelines. Look at how similar problems where done and see if you can generalize the methods that were used there. If you can, then you have just picked up another technique for your toolbox. Try to achieve the “understanding” described in the last section. This may help you get an idea that creates a new technique. Also you can just try random things hoping that something works. If something gets you somewhere, then try to figure out why it works. This is another way that new techniques are created.

Sometimes, despite everything, a problem cannot be solved. That should not happen to you in this course, but if it does then talk to me.

What Do I Need To Do?: At this point you have an “approach” or strategy to follow. Now you need to figure out exactly what you need to do to apply that approach to the problem at hand.

Try It: You now know very specifically what you need to do. There is no way to know whether it will work until you try it. With luck and experience, this step will be straightforward. If it does not work then you have only lost some time.

Note that in the process of doing this step you may find yourself faced with another proof that is hard enough that you have to go through this whole process to do it. If these “intermediate” proofs are too long, or break the train of thought in the proof, then you may want to consider proving these steps as lemmas in your final presentation of the proof.

Am I Frustrated?: “You can beat your head against a brick wall for as long as you like. The wall won’t care, but your head might.” There are times that you need to take a break. Recognizing this is important.

Do Something Else: This means exactly what you think it does. It is not always an option, but then again, none of you will ever put things off until the last minute...right?? Also there are times that things just need to sink in for a while.

Incidentally, if there are several parts to the problem, then it is often a good idea to try another part at this point. If you get it then you get the feeling that you are getting somewhere. Also it often happens that one part of a problem will give you an idea that you can use on the other parts. And it is usually the case that one part of the problem is significantly harder than the other parts.

Am I Done?: You have just done one piece. There may be other pieces. Remember that one of the most common mistakes is to do part of a problem, think that you are done, then go on to another problem. At this point it helps to look back at how many pieces you had to do, and see which ones you have done.

Write It Up: You have done the mathematics, but you still need to put it in a nicely written form. This is the stage where you figure out how to organize things, and make decisions such as which parts to call lemmas and which parts to leave in the main proof. You also need to check your wording and spelling. Also, as you are writing it down, you should double-check your work and reasoning.

Done: At this point you are done with the problem. But I am sure that you have no shortage of other ways to spend your time...

A Request:

I make no claims that the procedure that I just described will work for you. It happens to work for me, and for students when I tried this before, but people differ. Therefore I want to hear whether or not my giving this advice helps you personally to do proofs, and any ideas on how the advice can be improved.