How I do Proofs

I was looking through some old papers, and decided to put online some advice that I gave many years ago about how I tackle mathematical proofs. The advice is at How I Do Proofs. This is only lightly edited from the original that I handed out to a course I was teaching in the late 90s.

The course is the one I described at Teaching Linear Algebra. I never got any feedback on my request for improvements, but judging from how well that class did at proofs I believe that the advice was helpful. As one student I asked put it, "Doing proofs is like filling out a shopping list." That is how it should be in a first course where you are learning how to do proofs.

The class where I introduced this advice was fun. I started by handing out printouts of the advice. I then went through the flowchart at a high level. And then I put up a routine theorem from the text, which was the next thing I was supposed to do in the course. And I said, "OK, now that you've all learned how to prove things, you're going to prove this."

You should have seen the shock on their faces! Some started complaining. So I said, "No, seriously. You will all prove this. Just wait and see. It will work."

Then I began. I asked the one person to say what the first step was. A second person to do it. A third person what the next step was. A fourth to do it. And so on. And every time they did something that could be written down, I wrote down exactly what they said. Before long they had proven a result that none of them thought they could prove!

The third of the homework for that night which was on that day's material (if this statement puzzles you, go back to Teaching Linear Algebra and read about the homework strategy in that course) was very heavy on doing proofs. And I can tell that they referred to the handout by one fact. The next day the grader came to me, very puzzled, and asked me to explain this strange piece of reasoning that everyone had used. It was the contrapositive, which is an interesting alternative to proof by contradiction. One of the problems could be solved either with contradiction or the contrapositive, and they all chose the contrapositive because I'd listed it before contradiction.

I considered this a very good thing. One of the major problems that students have with proof by contradiction is that it works too often. Proofs that require a bit of routine algebra or computation can always be rewritten as proof by contradiction. The rewritten proof is correct, but it is unnecessarily confusing and it is better not to have used contradiction. However because contradiction seems to always work, it becomes a sledgehammer that the student always uses. Without noticing that it is sometimes the wrong tool.

The contrapositive doesn't have this drawback. It can solve the same problems as those that "really" needed proof by contradiction. But it doesn't lend itself to solving problems that never needed proof by contradiction. And so students who have been trained to try the contrapositive do not tend to make their simpler proofs over-complicated.

In fact when I drew up the advice I nearly left out contradiction. But it is so widely used that I figured I had to include it. However I tried to subtly discourage its use. And to the best of my knowledge I succeeded, I'm not aware that any students in my class ever used it in any of their proofs.

Teaching linear algebra

In a recent Hacker News post I made reference to an interesting teaching experience I had in the mid-90s. This is a longer explanation of the same.

I was a graduate student in math at Dartmouth College. I wound up teaching an introduction to linear algebra course that was also the first course where students were asked to do proofs. The class was somewhere in the range of 15-20 students. If I remember correctly, this was in the fall of 1996.

In preparation for the class I set myself goals around how well the students would learn the material taught. After some thought I settled on four ideas that I would use:

1. Homework not present at the start of class would not be accepted. However students were only graded on the best 20 out of 27 possible homework sets.
   
2. All homework sets were cumulative. Generally 1/3 was the current day's material, 1/3 from the last week, and 1/3 from anywhere in the course. Those thirds were in increasing order of difficulty.
   
3. Every class would start with a question and answer session to last no less than 10 minutes.
   
4. Every student could expect to be asked at least one question every other class.

These ideas may seem odd, but there was a method to my madness. Here is each idea explained.

1. Homework not present at the start of class would not be accepted. However students were only graded on the best 20 out of 27 possible homework sets.
   
   The point was to make sure that class started on time, with everyone ready to pay attention for question and answer time. I also didn't want to deal with people doing homework during lecture, evaluating sick excuses, etc. The leniency of not having to turn in 7 homework sets compensated for the rigidness of the policy. And cumulative homework sets meant that I didn't have to worry about students not practicing any given day's material.
   
   This worked even better than I hoped. The downside was that I had an argument on the second day when someone came in 2 minutes late and was not allowed to turn in his homework. But the first complaint was the last, and the students liked the freedom to decide when something else took precedence over doing homework.
   
   
2. All homework sets were cumulative. Generally 1/3 was the current day's material, 1/3 from the last week, and 1/3 from anywhere in the course. Those thirds were in increasing order of difficulty.
   
   This was the most important idea I wanted to try. I had long been aware that research on memory had demonstrated that when you're reminded of something as you're forgetting it, it goes into much longer term memory. As a result periodic review at lengthening intervals is very effective in increasing long term recall. A typical effective study schedule being to review after half an hour, the next day, the next week, then the next month.
   
   Now of course you can tell students this until you're blue in the face - but they won't do it. However when the study schedule is disguised as homework, they don't have a choice.
   
   This really seemed to work. What I noticed on tests is that students were noticeably shaky on material they had learned in the previous week, occasionally didn't remember stuff for a half-month before that, but absolutely nailed every concept that they'd first learned at least 3 weeks earlier. I credit the forced review schedule from cumulative homework sets for much of that.
   
   
3. Every class would start with a question and answer session to last no less than 10 minutes.
   
   For me this was the most important part of the class. The questions that came up in this session were my opportunity to refresh people on what they were forgetting, and were how I kept track of what topics should come in for more review on future homework sessions. Given my knowledge of how critical review is to learning, I honestly felt that time spent answering questions was more valuable than lecture. As long as there were questions, there was no maximum on how much time I was willing to spend on this.
   
   Of course the challenge is getting students to ask questions. My strategy was simple: I told them that someone will ask questions and someone will answer them, but they don't want me to be the one asking questions. On the second day nobody asked me any questions and I had to demonstrate. I picked a random person and asked her to explain a key point from the first day's lecture. She couldn't. I asked another student the same question. Again difficulty. I asked if everyone was sure that they had no questions. Someone asked me the question that I had been asking everyone else. I answered the question, answered the follow-up, and the point was made. I never again had to ask a question during question and answer period. :-)
   
   
4. Every student could expect to be asked at least one question every other class.
   
   My goal here was to be sure that every student was awake and following the lecture. It was never my goal to embarrass anyone or put them on the spot. To that end I developed a rhythm. Every few minutes I'd stop, say, "Let's make that a question," ask the question, pause so everyone could think through the answer, then ask a random person the question. I made sure to rotate people around so that everyone got their turn fairly.
   
   The questions I'd ask were always straightforward. They were things like, "What is the result of this calculation?" Or, "Why is this step OK?"
   
   I treated failure to get the answer as my failures, not theirs. If they couldn't get the answers then they weren't following the lecture, and I needed to slow it down, figure out the rough spots, etc. It might seem that the constant interruptions were slow. But I found that having everyone pay attention more than made up for it. The class as a whole moved as fast as any other class - but with far greater comprehension. And the interactivity made the class become very open about asking questions.
   
   As a bonus I managed to convince the entire class that taking notes was not worthwhile. I learned this lesson about math in first year undergrad. What you do is read ahead in the textbook. If you really want a set of notes, you can make them from the textbook before class. Then show up at class having read the day's material and ready to pay attention. Then if anything that the professor says doesn't make sense to you when you're paying attention and have already read the day's lesson, then ask the question then and there. If you don't understand it, then probably nobody else does either. Add to that periodic reviews, and you'll have a huge edge in any math courses.
   
   Nobody ever believes that that works. But this class had no choice because there is simply no way to take notes and pay attention at the same time. Which meant that the note takers couldn't answer questions. But within a few days they learned to not take notes, and I believe did much better for it.

So how well did this package work? As far as my goals were concerned, much better than I had dreamed possible. What really brought this home was the final exam. Based on class performance I drew up a test that I though was a fair test of what I thought they understood. I showed it to some fellow graduate students. They thought I was crazy. They thought the class would bomb, and were willing to bet me on whether anyone would get the bonus question.

The class aced the test. That bonus question? 70% of the class got it. I don't remember what the bonus question was, but I do remember another one that I thought was cute. It went like this. Let V be the vector space of all polynomials of degree at most 2. a) Prove that d/dx is a linear operator on V. b) You can put a coordinate system on V by mapping p(x) to (p(0), p(1), p(2)). (Please imagine that flipped 90 degrees so it is a column.) Find the matrix that represents d/dx in this coordinate system. My fellow grad students got me worried that this might be too advanced for an introductory linear algebra courses. But I needn't have worried - the only significant errors were minor arithmetic mistakes in the calculation. And I think I dinged someone for not having enough detail in the proof.

Furthermore I was lucky enough to talk to some of my students about the experience a few months later. The general consensus was that the material really stuck. Furthermore nobody studied for the final. No joke. As one girl said, "I tried studying because I thought I should, but I gave up after a half-hour because I already knew it all." That is how I think it should be - if you study properly through the course, then you won't need to study for the final. Because you've already learned it. And you'll have a leg up on the next course because you still remember the material that everyone else has forgotten.

So were there any downsides? Unfortunately there were some big ones. I had set goals around learning. I failed to set any around happiness. Having to pay attention during class was hard on the class. Also it motivated them to work hard. Since everyone worked hard and they thought that I was going to grade them on a curve, there was a lot frustration that they wouldn't properly be recognized for their work. (In fact I gave half of them A's in the end.) This frustration showed up the teacher evaluations at the end of the course. :-(

Therefore if I had to do it over I'd ask somewhat fewer questions, hand out a lot more compliments, make it clear that I would not grade on a curve, and if they performed anything like that first class, I'd be even more liberal with good grades. Of course the point is moot since I've found myself profitably displaced from math to software development. But if anyone decides to replicate my experience, I'd recommend paying more attention than I did to those issues.