2 4 Practice Writing Proofs

Proof

Proof-writing skills are important for all college-level math. Simply there's a special relationship between proofs and discrete math. In the "Goals of a Discrete Mathematics Course" department in the preface to his textbook, Rosen puts Mathematical Reasoning first in the listing. He writes:

Students must understand mathematical reasoning in social club to read, embrace, 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 amalgam proofs are addressed.

Rosen Chapter i 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 capacity 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. Hither is a procedure I employ to get the most out of these exercises.

How to Prove Information technology

This article isn't exactly well-nigh how to prove theorems. (See the Velleman book for that). Instead, information technology'southward 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 tin I practice a problem I don't know how to solve? It'south certainly worth studying problem-solving techniques. However, a good practice process is as useful as any trouble-solving heuristic. By practicing many types of problems at the right level of difficulty, y'all naturally option up trouble-solving skills.

The Procedure

Here's a half-dozen-footstep process for improving your proof-writing skills.

Step 1: Find a proof to practice

You can detect the best practise proofs in the main text of a textbook that'due south written at your level. If yous utilize a proficient textbook, these proofs volition have skilful explanations. You might also find explanations of the aforementioned proofs online, but every bit with any online source you have to be conscientious about quality. A textbook from a major publisher volition take gone through multiple reviews from experts, and you tin can find reviews from students online to see what they remember of it.

Some other 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 skilful solution manual can provide more detail.

Finally, you could use exercises that you don't take answers for, simply that tin be problematic if you don't accept someone to give you feedback on your work.

If y'all're taking a class, the professor does Step 1 for you, and y'all also accept a built-in source of feedback.

Stride 2: Brainstorm

For any moderately hard proof, it's unlikely that you'll be able to start with the premise and proceed step by step until yous reach the determination. And then y'all demand some way to come upwards with ideas on how to arroyo the proof.

Some options:

Compute specific examples and run into if y'all can discover whatsoever patterns.
If the proof is from a textbook, review definitions and theorems from earlier in the section or chapter.
Commencement with the premise and manipulate it in a style that seems to go closer to the conclusion.
Start with the conclusion and manipulate it in a way that seems to get closer to the premise.

Step three: Write a draft

One time your brainstorming seems to be leading somewhere useful, try writing a kickoff draft of the proof. In this version, you should take a good thought of why each step leads to the next. When you read through the complete draft, information technology should seem similar a reasonable argument. If y'all become stuck, return to Stride 2 and repeat every bit necessary.

Stride 4: Fill up in the details

You can write a proof at varying levels of detail depending on the intended audience. If y'all're writing for a mathematical journal, you lot might skip proof steps that you assume the practiced audience tin make full in. For a college class, I like to err on the side of providing too much detail in my answers. One time in a graduate Theory of Computation class, I was presenting a proof almost Turing machines and the professor asked me to skip a few slides because I was going over details that the form already knew. I don't know if they really did, and I still think it's better to explicate things too much than two little. Just you accept to go along your audience in mind.

If you're preparing a problem ready to turn in for a class, this step is an opportunity to read through your draft proof and provide more than explanation for steps that might not seem as obvious equally when you first wrote them. You might also convert your written proof into $\LaTeX$ if you have fourth dimension. Seeing information technology nicely typeset might encourage you to perfect your argument. And simply the deed of writing it again can make errors more obvious.

If you're practicing on your ain, there's less incentive to smoothen your proof. Only this is still a good time to verify that yous're convinced by your own argument. Once you lot move on to the adjacent step and look at someone else'southward solution, especially one written by an expert, in that location's a temptation to accept that as the proof. But mathematicians can show theorems in multiple ways, and so yours tin can exist different and notwithstanding be correct. The time when you're however working on it is a unique chance to use your unique feel to invent your own proof, even if you later discover that someone else found it hundreds or thousands of years earlier.

Step five: Read someone else'south version

The best way to larn from your do is to have an expert evaluate your work and advise areas for improvement. Only if that'southward not an option, information technology's all the same worthwhile to see how an expert (like a textbook author) proved the theorem that you just finished proving.

Specially if the proof you're reading is a concise respond at the back of a textbook, it's important to read it the aforementioned way you read critical sections of the textbook: become line by line, make full in any gaps, and generally write your own version of information technology. When you're done, you should be able to follow the author'southward proof as clearly as you follow the final version of your own proof. If the author took the same approach every bit you, this might be as elementary as comparing your proof with their proof and ensuring that yours has at to the lowest degree every bit much detail as theirs does. If their proof is very different, then y'all may have to do some research to understand their argument, at which point you lot can decide which version y'all like best.

Pace 6: Practise it later

Equally with whatever other math skill, if y'all desire to actually larn a proof, you have to practice it more once. In his classic weblog 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 certain he could prove all of them on demand.

Completing the prior steps gives yous one or more detailed proofs that you lot can employ as source material for learning a mathematical topic in detail. Completing this terminal footstep gives you lot more return on your learning investment by solidifying the proof technique in your mind, to be deployed in the future when you need information technology.

I'm writing about discrete math and competitive programming this year. For an introduction, see A Project for 2019. To read the whole series, encounter my Discrete Math category page.

(Image credit: Euclid)