I was taught in 9th grade the two column proof, and it wasn't until 11th (when I saw some number theory) that I realized what a poor method that is. However, it is certainly effective in getting simple statements proven. Since improving one's ability to write proofs is always helpful, and because helping others is fun, I was wondering if there is a better way to teach/learn proofs. Repetition works for induction, and contradiction in many cases, but how does one get good at coming up with the non-obvious approaches. Thanks.
Coursera has a periodically taught course by a rather famous Stanford professor about mathematical thinking that you might of interest the next time it's offered: https://www.coursera.org/course/maththink
I would also suggest broadening your inquiry from "how to do proofs" to "how to solve mathematical problems and then demonstrate that your answer is correct" In that sense, books such as Thinking Mathematically: http://www.amazon.com/Thinking-Mathematically-2nd-Edition-Mason/dp/0273728911 (although the 1st edition is fine, and a lot cheaper) would be an excellent resource.
A good proof provides insight into the mathematical or logical structure underlying what you're proving. A mediocre proof merely demonstrates that it works all the time, without giving any new insight into what's going on. So I'd urge you to rely less on proofs, say, by induction and more on careful and thoughtful reasoning about patterns and why they must hold true for all cases. Mason will be a great start in doing that.
Also, a nice (if a bit heavy) article that a colleague just recommended to me about the importance of proofs that explain what's going on mathematically: Hanna, G. (1990). Some pedagogical aspects of proof. Interchange, 21(1), 6–13.
Three more books that might be of interest:
- Allenby, R.B.J.T. Numbers and Proofs
- Solow, D. How to Read and Do Proofs;
- Velleman, D.J. How to Prove it: A Structured Approach.
I think it's also worth bearing in mind that students who have learned earlier mathematics primarily as a set of procedures might not be in the right frame of mind to appreciate what proofs are for and why we bother with them. I wrote some chapters for such students (and for those with different experiences) in my book 'How to Study for a Mathematics Degree' (the US version is called 'How to Study as a Mathematics Major'). The book is based on research in mathematics education and psychology and it won't suit everyone, but it aims to explain how proof-based mathematics differs from earlier work, and how a student might go about tackling it.
This question is interesting because it points to what many of us believe is the problem with "introduction to proof" courses: Just because proofs have a common underlying logical architecture doesn't mean that new proofs don't require genuinely creative new ideas that are specific to the mathematical questions they address. An intro to proof course generally fails to give adequate weight to the very important fact that the idea for a new proof is most likely to come from the careful consideration of a very specific difficulty of a very specific problem. It's hard not to feel that such courses, by definition, don't correctly teach the heart of proof because they are general. Truly new proofs arise from careful thought that is spurred by a mathematician's encounter with a specific problem.
The OPs question reminds me of an image (I believe found in Derrida) used to describe the activity of structuralists as attempting to reproduce a beetle using only the beetle's shed shell. Introductory proof courses may give a false impression that reproducing the beetle from its shell is possible, and that there is a "method" for genuinely creative mathematical work.
I may be wrong, but it seems that the way to find genuinely new proofs is to develop expert knowledge about a problem in a field over a very long time, until what is needed eventually becomes clear. This is the same thing that is needed for the development of a useful tool in any other field.
How does one come up with the idea of a hammer, screwdriver or wrench? How does one come up with the idea for a turbine engine? How about a microprocessor? All of these require various degrees of deep familiarity with the contour of some problem combined with hard work, knowledge of one's field and a little bit of luck!
I am not saying there aren't healthy methods for getting better at mathematical research, but I am saying that there is no shortcut. I've asked a closely related question that might be interesting to you. It also might be worth looking at Terry Tao's blog.
Probably the best advice on this topic came in a short remark of Yitang (Tom) Zhang: "Just keep thinking".
There are resources on writing proofs, e.g. Hammack's "Book of proof" and many others. For mathematical writing style, look for e.g. Knuth, Larrabee, and Roberts' "Mathematical Writing" (MAA, 1989, a (somewhat mutilated) version here). I'm sure a search for lecture notes on intermediate mathematics courses will turn lots of hits.
In my experience, for beginners it is important to structure proofs in familiar ways (announce the overall strategy, do e.g. induction in styzed ways, don't skip steps), thus I can understand the idea of column proofs. But more interesting proofs aren't always easy to classify. For an astonishing collection of nice proofs see Aigner and Ziegler's "Proofs from THE BOOK" (Springer 2012, 4th edition). Most don't require calculus at all.
If you want them get interested (or want something to give more restless students) Dunham's "Journey though genius" (Penguin, 1990) or "The mathematical universe" (Wiley, 1997) would be good starting points.
Proofs are what make mathematics special as a subject. The sciences have theories which change with time. Mathematics has theorems that don't change with time. However, I think "teaching proofs" is over emphasized. Showing "samples" of proofs that illustrate different approaches to proving is much more important than being able to "prove theorems" as an output skill for a "course." Students should see proofs by contradiction, using parity arguments, using the pigeon hole principle, using induction, proofs without words, etc. Teaching students about using mathematical tools and ideas is much more important than teaching proofs it seems to me. No one is likely to be able to find a proof of the 4-color theorem using mathematical induction. However, Carsten Thomassen showed that plane graphs are 5-choosable, using mathematical induction in a clever way. (The issues is having lists of colors where the vertices can be colored using any color on the list for that vertex but the usual rule that two vertices joined by an edge can't get the same colors holds). (Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 62: 180–181) The idea of list colorings is more important to show students than getting them to master how to do induction proofs of statements that are already known to be true. Making interesting/important conjectures is very hard, in many ways, harder than proofs.
I tried to learn (teach myself) proofs by grouping them into categories. For instance:
1) Proof by contradiction: Assume the converse and show that it leads to contradicting the hypotheses, therefore the original must be true.
2) Proof by induction: This is basically a recursive argument.
3) Proof by common terms: Prove A= B by showing that they both "reduce" to a common term.
4) Construction and verication (c & v for short). Construct the formula, and verify that it has the desired properties.
5) Proof by completion: A is "too weak" to imply B, but A does imply B when you add a further condition, C.
And there's always the Polya admonition: "Invert!" Jacobi Inversion formula, LaPlace Transforms, deMorgan's Laws, etc.