How do you "get it" when it comes to proofs?

Question

When we start getting into algorithm design and more discrete computer science topics, we end up having to prove things all of the time. Every time I've seen somebody ask how to become really good at proofs, the common (and possibly lazy) answer is "practice".

Practicing is all fine if you have the basics down, but how do you get into the mind set for mathematical proofs? When did induction click? What resources are best for teaching these topics? What foundation topics should be researched prior to indulging in proof-writing?

Answer 1

They aren't being lazy, practice is the only way. Take classes you have to do proofs in and look online for class notes and old tests with answers from other colleges that go over proofs.

Answer 2

I'll start off my answer by admitting that as a CS student, I had a really tough time grasping a formal way of thinking, and it's never easy, unless you have a talent for it.

I'm afraid there is no better answer than practice and study.

A formal mathematical and algorithmic way of thinking and visioning problems is a skill which first demands a very deep understanding of the subjects you are dealing with. Second, it requires you have good knowledge of existing proofs. Try to envision yourself as some of the great scientists who came up with the algorithms you are studying. Understand how you would have tried to tackle that specific problem. Then see how they proved the correctness of their algorithm.

I can only recommend the greatest textbook in this subject which is Intro to Algorithms by CLRS. If you go through it from start to finish, including every exercise, you will enhance your skills.

Answer 3

Practice is really the only way, but it can helped along by reading proofs as well. I won't touch on practice because the other answerers have covered everything that I can think of, so I'll just talk about what I mean by reading.

Textbooks are very fond of writing out the "important" proofs. Its very nice, because they often prove very powerful statements, and are really fancy. But just as you shouldn't learn to be a world-class gymnast from day 1 by emulating an Olympian (as in, you'll probably break your spine), you shouldn't read any really big proofs (at first). What I found was helpful was reading smaller proofs, usually from returned homework (I assume you're a student) or occasionally a textbook that wisens up.

The reason why I think reading proofs is helpful is because there are a small set of "tricks" or "ideas" that constitute huge chunks of schoolwork proofs, and even more advanced ones. Data structure qualities and recurrence relations usually involve thinking related to proof by induction, proofs involving computability with finite state machines sometimes use the pigeonhole principle, and more rarely the idea of diagonalization (very infrequent, don't worry about it). And of course, just about every other proof uses proof by contradiction. I'm sure there are other handy tools that have slipped my mind, but I hope you get the idea.

Figuring out when, how, and why you'd approach a problem with one particular method or another is what takes practice and experience. I suggest reading proofs in addition to practice because it can often show you creative ways of using a proving method you've already encountered.

As a final note, try to remember when you first learned to program. How did you get better? Proving things and programming things are not too dissimilar, in my opinion. :)

Answer 4

You get into the mind set for doing mathematical proofs by becoming a mathematician. I don't mean the last statement in a tautological way, but realize that a mathematical proof, as published in a mathematical journal, is something of a rhetorical artifact; i.e., it is a proof because a body of mathematicians agree that it is a proof. Ideally, the arguments in the proof could all be reduced to symbolic logic, but this is not how it is done in practice. The utter failure of computer-generated proofs to do valuable mathematics provides some evidence for this.

I get into the mind set by doing proofs and having them accepted by other mathematicians. I agree with the others that "practice" is essential. You don't do proofs unless you try, try, and try. Often the light dawns slowly.

The best resources are, of course, other mathematicians, and reading proofs. There are very few, if any, who can do true mathematical proofs without being part of the mathematical community.

Answer 5

I'm afraid that "practice" really is the best answer here.

Its very similar to programming: once you get the hang of it, you find patterns which solve problems particularly well, and you can create a picture of the high-level design of novel systems which you've never implemented before. However, neophyte programmers aren't aware of patterns: they hack away at code until they accidentally stumble on some solution which appears to "work".

When you're given a problem to prove, you can usually identify properties ("Do I have a set of distinct objects?", "Am I generating permutations?", "Am I looking to minimize/maximize some value?", etc). Sooner or later, proofs will clump together into vaguely similar group, where techniques used to solve one problem can easily apply to novel variations.

Recommended reading:

• The Algorithm Design Manual by Steven Skiena.

Answer 6

I have no idea. Probably the same way you get good at composing music.

When I try to prove something I'm not following some fixed strategy, I just think about the problem. Then [undefined amount of time] later, my mind returns a result and I jump up to write it down.

But practicing definitely helps. When I started trying to prove extremely simple statements, like DeMorgan's laws, I was completely hopeless. So I sat down and did the fifty or so optional example problems on a worksheet we were given. Now it feels natural to prove something.

Answer 7

Practice and study makes perfect sense, agreed. Some tricks, that I found useful:

1. Make notes on everything you study (I've tried just to read books -- a lot of material just passes through).
2. In addition to previous point: do all (or most) proofs by youself, use book/lecture notes as a guide; a lot of proofs contains phrases like "we can see now, that XXX". And XXX is not always trivial conclusion.
3. Make exercises; for example, in CLRS book there are dozens of exercises. Exercises are good way to get the ideas behind algorithms/correct proofs.
4. If you want to better understand the internals of algorithm -- consider participating in online programming contests like UVa's.