Proof-writing skills are important for all college-level math. But there’s a special relationship between proofs and discrete math. In the “Goals of a Discrete Mathematics Course” section in the preface to his textbook, Rosen puts Mathematical Reasoning first in the list. He writes:
Students must understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments [proofs]. This text starts with a discussion of mathematical logic, which serves as the foundation for the subsequent discussions of methods of proof. Both the science and the art of constructing proofs are addressed.
Rosen Chapter 1 is “The Foundations: Logic and Proofs,” and that chapter ends with sections on “Introduction to Proofs” and “Proof Methods and Strategy.” A textbook that specifically covers proof techniques, Daniel J. Velleman’s How to Prove It, begins with chapters on these same topics, and includes chapters on logic and on mathematical induction which Rosen also covers. So it’s not surprising that many of the exercises in Rosen ask for proofs. Here is a process I use to get the most out of these exercises.
How to Prove It
This article isn’t exactly about how to prove theorems. (See the Velleman book for that). Instead, it’s about how to practice proving theorems. I ran into this distinction several years ago when I wrote an article called How to Attack a Programming Puzzle and got feedback that essentially said: how can I practice a problem I don’t know how to solve? It’s certainly worth studying problem-solving techniques. However, a good practice process is as useful as any problem-solving heuristic. By practicing many types of problems at the right level of difficulty, you naturally pick up problem-solving skills.
The Process
Here’s a six-step process for improving your proof-writing skills.
Step 1: Find a proof to practice
You can find the best practice proofs in the main text of a textbook that’s written at your level. If you use a good textbook, these proofs will have good explanations. You might also find explanations of the same proofs online, but as with any online source you have to be careful about quality. A textbook from a major publisher will have gone through multiple reviews from experts, and you can find reviews from students online to see what they think of it.
Another source of practice proofs is odd-numbered textbook exercises, which often come with answers. However, answers to exercises are usually less detailed than discussions in the main text. A good solution manual can provide more detail.
Finally, you could use exercises that you don’t have answers for, but that can be problematic if you don’t have someone to give you feedback on your work.
If you’re taking a class, the professor does Step 1 for you, and you also have a built-in source of feedback.
Step 2: Brainstorm
For any moderately difficult proof, it’s unlikely that you’ll be able to start with the premise and proceed step by step until you reach the conclusion. So you need some way to come up with ideas on how to approach the proof.
Some options:
- Compute specific examples and see if you can detect any patterns.
- If the proof is from a textbook, review definitions and theorems from earlier in the section or chapter.
- Start with the premise and manipulate it in a way that seems to get closer to the conclusion.
- Start with the conclusion and manipulate it in a way that seems to get closer to the premise.
Step 3: Write a draft
Once your brainstorming seems to be leading somewhere useful, try writing a first draft of the proof. In this version, you should have a good idea of why each step leads to the next. When you read through the complete draft, it should seem like a reasonable argument. If you get stuck, return to Step 2 and repeat as necessary.
Step 4: Fill in the details
You can write a proof at varying levels of detail depending on the intended audience. If you’re writing for a mathematical journal, you might skip proof steps that you assume the expert audience can fill in. For a college class, I like to err on the side of providing too much detail in my answers. Once in a graduate Theory of Computation class, I was presenting a proof about Turing machines and the professor asked me to skip a few slides because I was going over details that the class already knew. I don’t know if they really did, and I still think it’s better to explain things too much than two little. But you have to keep your audience in mind.
If you’re preparing a problem set to turn in for a class, this step is an opportunity to read through your draft proof and provide more explanation for steps that might not seem as obvious as when you first wrote them. You might also convert your written proof into $\LaTeX$ if you have time. Seeing it nicely typeset might encourage you to perfect your argument. And just the act of writing it again can make errors more obvious.
If you’re practicing on your own, there’s less incentive to polish your proof. But this is still a good time to verify that you’re convinced by your own argument. Once you move on to the next step and look at someone else’s solution, especially one written by an expert, there’s a temptation to accept that as the proof. But mathematicians can prove theorems in multiple ways, so yours can be different and still be correct. The time when you’re still working on it is a unique chance to use your unique experience to invent your own proof, even if you later discover that someone else found it hundreds or thousands of years earlier.
Step 5: Read someone else’s version
The best way to learn from your practice is to have an expert evaluate your work and suggest areas for improvement. But if that’s not an option, it’s still worthwhile to see how an expert (like a textbook author) proved the theorem that you just finished proving.
Especially if the proof you’re reading is a concise answer at the back of a textbook, it’s important to read it the same way you read critical sections of the textbook: go line by line, fill in any gaps, and generally write your own version of it. When you’re done, you should be able to follow the author’s proof as clearly as you follow the final version of your own proof. If the author took the same approach as you, this might be as simple as comparing your proof with their proof and ensuring that yours has at least as much detail as theirs does. If their proof is very different, then you may have to do some research to understand their argument, at which point you can decide which version you like best.
Step 6: Practice it later
As with any other math skill, if you want to really learn a proof, you have to practice it more than once. In his classic blog post on studying discrete math as a student, Cal Newport describes creating a canonical version of each proof covered in his class, and quizzing himself on these “proof guides” to make sure he could prove all of them on demand.
Completing the prior steps gives you one or more detailed proofs that you can use as source material for learning a mathematical topic in detail. Completing this last step gives you more return on your learning investment by solidifying the proof technique in your mind, to be deployed in the future when you need it.
I’m writing about discrete math and competitive programming this year. For an introduction, see A Project for 2019. To read the whole series, see my Discrete Math category page.
(Image credit: Euclid)