Teaching undergraduate students to write proofs In my experience, there are roughly two approaches to teaching (North American) undergraduates to write proofs:


*

*Students see proofs in lecture and in the textbooks, and proofs are explained when necessary, for example, the first time the instructor shows a proof by induction to a group of freshman, some additional explanation of this proof method might be given.  Also, students are given regular problem sets consisting of genuine mathematical questions - of course not research-level questions, but good honest questions nonetheless - and they get feedback on their proofs.  This starts from day one.  The general theme here is that all the math these students do is proof-based, and all the proofs they do are for the sake of math, in contrast to:

*Students spend the majority of their first two years doing computations.  Towards the end of this period they take a course whose primary goal is to teach proofs, and so they study proofs for the sake of learning how to do proofs, understanding the math that the proofs are about is a secondary goal.  They are taught truth tables, logical connectives, quantifiers, basic set theory (as in unions and complements), proofs by contraposition, contradiction, induction.  The remaining two years consist of real math, as in approach 1.
I won't hide the fact that I'm biased to approach 1.  For instance, I believe that rather than specifically teaching students about complements and unions, and giving them quizzes on this stuff, it's more effective to expose it to them early and often, and either expect them to pick it up on their own or at least expect them to seek explanation from peers or teachers without anyone telling them it's time to learn about unions and complements.  That said, I am genuinely open to hearing techniques along the lines of approach 2 that are effective.  So my question is:
What techniques aimed specifically at teaching proof writing have you found in your experience to be effective? 
EDIT: In addition to describing a particular technique, please explain in what sense you believe it to be effective, and what experiences of yours actually demonstrate this effectiveness.

Thierry Zell makes a great point, that approach 1 tends to happen when your curriculum separates math students from non-math students, and approach 2 tends to happen math, engineering, and science students are mixed together for the first two years to learn basic computational math.  This brings up a strongly related question to my original question:
Can it be effective to have math majors spend some amount of time taking computational, proof-free math courses along with non-math majors?  If so, in what sense can it be effective and what experiences of yours demonstrate this effectiveness?
(Question originally asked by Amit Kumar Gupta)
 A: Although I don't speak especially from teaching experience, I think a good hybrid approach is to teach a combinatorics course which requires a lot of proofs. You're doing real math for its own sake, but it's a good subject to cut your teeth on serious proofs, because the definitions are clear and students don't have to deal with new abstractions at the same time.
A: I taught the `transitions' course at a large state university a number
of years ago, with reasonable success. 
The clientele of this (purely elective) course was mainly B students 
in calculus who would likely have done poorly in real analysis
or abstract algebra, and would have had difficulty completing a math major.
To maximize the impact on students' ability to understand and produce 
proofs, several things were important:
a) The text was Velleman's How to Prove It: A structured approach, 
which is readable by average students, clearly delineates the structure and
construction of typical proofs, and is full of problems which are 
elementary but not boring.  (For a regular beginning analysis class
I just ask the students to read this book---esp. chapter 3 as mentioned
by Jon Bannon---and I discuss the basics of this material 
for a few lectures.)
b) The format of most class sessions was discussion not lecture. To have these students passively listen, like in their
previous courses which they demonstrably failed to master, would be
useless.  Discussion was structured like in a humanities or language
course, led by the instructor with specific goals in mind and calling
on individual students to involve everyone and make sure they get it.
The 22 students were informed that it was essential that they come to 
class prepared, having read the day's material and having worked the
relevant problems, laid out in each week's syllabus.
c) Why we insist on ``proof beyond unreasonable doubt'' was explained,
referring to the great discoveries of 19th and early 20th century 
analysis (especially regarding infinite sets and fractals)
that demand the enormously skeptical approach to establishing truth
which now dominates much of modern mathematics.
Many of the students were weak at the start and apparently benefited
from all this. For one, this course was a big step in eventually
changing his career from fisherman to gaining a Masters and working in a scientific software company. Another later did A work in a senior-level ODE course I taught.
But I did not conduct a randomized controlled study.
A: I am teaching such a course - in a 4 week intensive one course at a time format - right now.  This is a reminder to myself to say something intelligent about it in February, and a placeholder for my future answer.  (If you see this in mid-February, a reminder to actually put up an answer will be much appreciated.  I am posting under my real name and can be Googled.)
One of the things I am thinking about now, 2 weeks in:
It has surprised me the extent that what one might simply call cognitive deficits are an obstacle.  Some of my students have trouble consistently being able to keep three ideas with their precise statements in their head at the same time.  (I mean to say that if they make a special effort for one or two statements, they can, but it is a struggle for them to do this routinely over even a short proof.)  This is a serious problem because when a step involves going from a statement with two quantifiers to another statement, the first statement with the quantifiers has already fills up their head and there is no room for the next statement.
What I am suggesting to my students, with absolute seriousness, is to do a Sudoku puzzle or two every day, preferably with a pen (to force themselves to think through inferences rather than going by trial and error).  The inferences involved in doing Sudoku might be quite simple to most of us, but you do have to keep a few facts in your head simultaneously to make the inference, and I am hoping the practice does improve their working memory.
A: I am just stepping into the teaching world, and finished my first semester as a teaching assistant in an introductory course in set theory and logic, which is giving a formal background to induction, order relations etc. etc..
I can give my own insight as someone who finished his undergrad degree recently. In my university it is mainly the first method for math students. We see proofs, we are given questions which are mostly about proving or disproving things. By the third year I think that everyone in my class (well, we were quite a small class to begin with) knew very well how to write a mathematical proof.
The second approach you described sounds a bit problematic to me, and I'll tell you why. I took a course in functional analysis. Other than the name of a few theorems, and maybe one or two theorems which I actually remember the contents (but not a single proof) I remember pretty much nothing of the course. Same can be said on the course I took in number theory (though I remember slightly more from that one), and on other topics. It's not all bad, when my friend who's taking a related course asks me a question I usually amaze myself by being able to supply a partial answer, and if I ever encounter the material it's easier to go through it. However, I still don't remember much. Giving someone a course in "How to write proofs" means that for some it will stick, and for others it won't stick - and they won't be able to wake up in the middle of the night and give a formal proof to some theorem they will later name "The Dreaming Lemma"; while in contrast it will take a long time for someone who spent three (or more) years just seeing proofs and writing proofs to forget that method, and not to mention the bonus for deep critical thinking which allows you to be able to scratch off ideas even before they reach your mouth or hands.
That been said, I do think that the second approach is very good when you want to focus on teaching mathematics in a lower level (i.e. non-academic level, or even low level math course to philosophy students) or if your students are in applied mathematics program, or something like that. I don't see how many set theorists and logicians will grow from this sort of method, but I might be wrong and even if I am right - not everyone loves set theory.
A: This is a great question.  In fact, I hope people won't think it over-dramatic if I call it one of the great math education questions of our time.
At the University of Georgia, we have decided as a department to follow the second approach: we offer a course Math 3200: Introduction to Advanced Mathematics.  This is one of our three "transitions" courses, the others being (Math 3000) linear algebra and (Math 3100) sequences and series.  But this is not to say that the faculty here are unanimously enthusiastic about approach two: in fact I have heard more dissent than agreement among the (mostly young, as it happens) faculty with whom I have discussed the matter.
I myself taught this Math 3200 course twice in recent years: here is my course webpage (don't get too excited: it only gives a very limited picture of what the course was about).  I was somewhat bemused when I taught this course for the first time, since this is not a course I have ever taken.  For instance, we spend about three weeks of the course on mathematical induction, a topic which I learned in high school.  (More precisely, I learned about it during a self-paced summer Algebra II course I took through the CTY program after my freshman year of high school.  It wasn't until years after that I began to understand that -- in that I actually read, did problems on and was tested on the entire Algebra II book -- I actually learned rather more than what takes place in an actual Algebra II course even at my (very good) high school.)
And yes, the course began with a chapter on logic: truth tables, contrapositives, negating statements, and so forth.  I was surprised to discover that many of my colleagues found this material to be dry, pointless and difficult to teach.  (Some of them even affected not to be able to easily solve some of the logic problems that appeared on later exams.  I do think this was an affectation, and a curious one.)  But for my part I very much enjoyed teaching the course and most certainly did not find it a waste of time: spending say, two weeks setting up logic is a small price to pay for being able to expect that students will not confuse the converse with the contrapositive for the rest of their careers.  And I confess that I did not in fact find it boring: I remember deciding at one point to draw one big table with all $2^{2^2}$ different binary connectives and ask the students to give the simplest description they could for each one.  This took most of a class period, but compared to, say, finding the rate of change of the length of some guy's shadow at the instant he is 10 meters away from a lamp post, it was great fun.
I believe this course was very useful for the students: it is nice to have one course where one can spend as much time as one needs concentrating on the processes and methods of proofs themselves, rather than on proving particular theorems.  (Which is not to say that we didn't prove anything at all: there was a unit on divisibility and another on modular arithmetic, for instance.  When I have taught undergrad number theory, I assume that students have seen this material twice over: in this course, and then again in the required semester of abstract algebra, and I really don't cover it again.)  Moreover there was time to concentrate on the students' writing in particular, and may Gauss strike me down if the writing didn't improve from horrible to halfway decent throughout the course of the semester.
This course is certainly not appropriate or helpful for all undergraduate math majors.  For instance, we offer one section of Honors Calculus a la Spivak per year (I have the good fortune to be teaching this course next year: a year free of lamp posts!) and I think that students who do well in this course learn everything that we would like them to learn in the Math 3200 transitions course and more.  But for a certain level of student -- a level that can be trained to do well as an undergraduate math major -- this course works very well.
Added: after rereading the question, I want to make clear that the above long answer is not an argument for option 2. versus option 1.  Option 1. -- i.e., include proofs in all university level math classes, presumably in an increasingly sophisticated way as the classes progress -- which in my understanding is standard in most European university curricula, is not even an option on the table at my (and, I think most) American universities.  (I was an undergraduate at the University of Chicago, and that was definitely an exception to the rule.  Not only did I have classes which concentrated somewhere between primarily and exclusively on proofs from the very beginning, but in fact all calculus classes there insist on treating some theoretical aspects, including about a month of class time on epsilon-delta proofs.)  So my answer takes as a given that there is a transition being made from almost exclusively computational courses to somewhat theoretical courses.  Given this, the question is whether this transition should be done in exclusively in the context of content-based courses (e.g. linear algebra with careful definitions and proofs), in the context of an "introduction to proofs" course, or both.  At UGA, our answer is "both".  What I am saying that in my opinion the "introduction to proofs" course is not a waste of the students' time.  Some others feel differently.
A: I have tried teaching proofs for years, and I have had a lot of trouble, both in "proof" courses, and in ordinary courses.  The hard part for me was getting the student to think about what the statements meant, and why the statements implied each other, rather than just memorizing a sequence of steps.  Often we mathematicians do not notice that we are leaving out remarks that are logically essential, because we know how to fill them in.
Students "learn" much more easily to repeat even lengthy proofs that do not reveal any reasoning, than to give even short arguments that require it.  E.g. most students can easily learn the sequence of steps that claim to prove the product rule in calculus.  But a quick examination of even many of the best books will show that the logic of the proof is not made clear even by the author.
E.g. the proof usually starts out with the difference quotient of the product, and the word "limit" in front of it, and then manipulates the difference quotient until it becomes separated into the appropriate two separate limits.  No mention is made of the fact that the limit which is being taken for granted in the first part of the discussion is not known to exist until the end.  Hence the proof should correctly be done only with the difference quotient and not the limit of it, or else it should be stated that the word "limit" is not justified until the end of the argument, by reading backwards.  This logical gap occurs even in the magnificent book of Spivak, (but not in that of Apostol).
I.e. the students can learn to derive the formula, but do not appreciate even the need to show the derivative of the product actually exists.
Similarly algebra students "learn" to give the proof of the rational roots theorem, by simply multiplying out the denominators, but at the least step, where some words need to be used to justify a divisibility statement, (powers of relatively prime numbers are still relatively prime), they slough over it.  They have much more trouble with irrationality of a square root, because more justification is needed. I have had students in number theory learn the elementary proof that sqrt(2) is irrational, by showing first an integer is even if its square is, and yet not be able to extend it to sqrt(3).
Once I noticed that since polynomials are "symmetric" in a sense, the reverse of the proof of Eisenstein's criterion would yield a proof of the reverse criterion, where p^2 does not divide the lead coefficient instead of the constant term.  Only one in a class of over 30 abstract algebra students was willing to attempt this challenge problem, and that one never got it, even with several days of email hints.  If a student cannot give this reverse but otherwise identical proof, how much does he understand of the original proof?
This suggests to me that proofs involving words are crucial to learning reasoning, and one should take great care not to assume that a sequence of correct symbols implies understanding of the logic.  I would enjoy being able to sit in Pete's course and observe how he handles it.
I am not too impressed with most books teaching proofs.  Often it seems the author is going through the motions and not thinking about the consequences of his statements.  In one I received, they discussed bounds and least upper bounds and claimed it was obvious the natural numbers are an unbounded set of reals without relating the two concepts.  Then later they made a big deal out of proving the archimedean property for the reals, but without linking it to the earlier equivalent but unjustified statement about the natural numbers.   This undermines a good student's faith in the importance of the topic. 
I got my own initiation first in high school, from a brief course in propositional calculus, and then from a Spivak type course at Harvard from Tate where the homework was all proofs.  Then came Birkhoff and Maclane, and finally Loomis and Gluck reinforced it by a very clear use of quantifiers in lectures on real analysis and differential equations.  There were no "proof" courses at Harvard in 1960.
I agree 100% with the questioner who asked how the students could be expected to have understood the first two years of math without seeing the logic until junior year.  I would love to have that course moved much earlier.  Having it in high school was great for me.  And I also lived before proof was removed from high school geometry.
A: Regarding different flavors of approach 1, here are some words from Halmos.
I have taught courses whose entire content was problems solved by students (and then presented to the class). The number of theorems that the students in such a course were exposed to was approximately half the number that they could have been exposed to in a series of lectures. In a problem course, however, exposure means the acquiring of an intelligent questioning attitude and of some technique for plugging the leaks that proofs are likely to spring; in a lecture course, exposure sometimes means not much more than learning the name of a theorem, being intimidated by its complicated proof, and worrying about whether it would appear on the examination.

Many teachers are concerned about the ... amount of material they must cover in a course. One cynic suggested a formula; since, he said, students on the average remember only about 40% of what you tell them, the thing to do is to cram into each course 250% of what you hope will stick. Glib as that is, it probably would not work.

Problem courses do work. Students who have taken my problem courses were often complimented by their subsequent teachers. The compliments were on their alert attitude, on their ability to get to the heart of the matter quickly, and on their intelligently searching questions that showed that they understood what was happening in class. All this happened on more than one level, in calculus, in linear algebra, in set theory, and, of course, in graduate courses on measure theory and functional analysis.
A: I taught a fourth-semester course called "Introduction to Analysis," in which we looked at differential calculus for a second time, stressing the foundations, the logical structure, and proving all the key theorems. We used Stephen Abbott's excellent book, Understanding Analysis. 
The course was intended primarily for math majors, although we had some interested students from other programs. Becuase we had 8 – 12 students each time I taught the course, I thought it would be a pity to lecture. So I ran the course as a seminar. I would lecture briefly to begin and end each chapter, and then I assigned problems from the textbook, for which the students had to present solutions in class. I would sit at the back of the class, and observe the discussions that took place after the presentations. Typically, if an error were made in a proof, the students wouldn't necessarily notice right away. Instead, someone would ask, "Could you explain again how you got from line 3 to line 4?" or some such question. The presenter would typically struggle to explain the point, and within a few minutes everyone could see that there was something wrong. If the group could patch up the proof on the spot, great. If not, I would send them away, sometimes with a hint, with the task of fixing it up and presenting it again next time. 
As long as all the points that I wanted to be discussed were actually discussed, I would stay silent. Of course, if not all the relevant points were brought up, I would ask questions to move the class in the direction I wanted them to go. 
The feedback I got from students was interesting. They told me it was much more work than a regular class, but they learned a lot more than in a regular class, too. I think this has implications for all of education ... it's a key reason why lecturing to 500 students is largely ineffective, no matter how brilliant the lecturer. I took this feedback as evidence that this method of teaching proofs can be effective. 
Secondly, a comment about calculus/analysis textbooks: the vast majority of them provide no training in the kind of thinking needed for creating proofs. (This is the reason that commenters refer to specialist books (Polya is great, as is Proofs and Refutations by Imre Lakatos), not standard calculus texts.) They simply provide finished products, often very tersely, without any sense for the thinking that goes into shaping a proof. Abbott's book is a lovely counterexample. At a higher level (for analysis, anyway), T.W. Korner's A Companion to Analysis is beautiful. The first few pages of this book provide tremendous motivation for the need to prove seemingly obvious theorems.
My point here is that writers of standard textbooks can learn a lot about how to make sections on proof much more effective. Part of the problem is that publishers want to please everyone, to maximize profits, and so they tightly restrict page count while trying to cram in as much content as possible. As in classrooms, cramming in as much content as possible is counterproductive to good teaching and learning.
A: As an undergraduate, I have no experience with the teaching side of this question, so I might not be able to answer it properly.
However, I do feel very strongly about option (1) because of my own experiences, so I'll quickly mention them as it may be of some use:
In my high school we did very few proofs.  I did AP calculus, which I did enjoy, but not to the same extent as physics.  Before University I had no intention of going into mathematics, mainly because of several ill-conceived views of what it actually was.
However in first year, things changed a lot.  My honors course was completely proof based, and we were taught calculus rigorously.  There was also a weekly problem-solving session (Putnam) where improving at proving was the emphasis.
Later that term, I realized I wanted to learn more, so I picked up Rudin 3E and began to read it.  The chain of events that followed over the next year made me decide to do a degree in math (particularly my summer project).  I remember feeling that "I had never seen mathematics before," because proving things in Analysis and Algebra (however basic) does require a very different style of thinking.
Anyway the point that I'm trying to get at is if in my first year we had not done any proofs, I would not have applied to work in math for the summer, or had the desire to read about it on my own.  I probably wouldn't be doing a degree in honors math right now (it is likely either engineering or physics).
I have personally found a trend, the higher the level the course, the more aesthetically pleasing the material is.
So how can people want to go into mathematics when they haven't seen as many of the real reasons that people pursue it. 
(and the really pretty reasons too)
A: Let's say you choose 2.  This is a sort of motivation-less course, naturally - all the things that will be proven, or at least many of them, are somewhat obvious to people who have lots of math experience, which the typical person to make it that far in the math curriculum will be (see David Bressoud's talks, of which that is one, for some fairly troubling statistics).  
Okay, but you can turn that on its head.  The reason such things are obvious (early in such a course, for instance, one usually proves that if $p|n^2$, then $p|n$) is because one has played with numbers a lot.  So giving students something new in which to develop context and intuition is a great idea.  Graph theory is a standard place to do this - proving easy things about colorings or connectivity - but one could introduce the groups $\mathbb{Z}_n$ or something with a little more structure than one initially thinks. 
I saw a great talk where proving things about the decimal expansion of numbers was a big part of such a course.  This can get into primitive roots, surds, etc., if you're ambitious - or just provide something a little off the beaten path.
Now, this doesn't look like an answer to your question, but it is.  Namely, now that no one knows quite what the right answer is, the whole class can work together to make a proof that they all believe (and if they're wrong, you put it on the test).  This isn't quite Moore method, but is of course influenced by it.  Or you can make a journal for such things and give them feedback, or whatever you like.  It's not the usual technique for teaching proof-writing, but is more realistic and can be easily complemented to the techniques you're currently studying (e.g., some graph theory stuff pretty much has to be proved by induction).
And something they've created from scratch is going to be much more effective in figuring out how to attack a proof.  The key is that this will not be successful without doing it fairly consistently - not necessarily every day, but providing a consistent (perhaps weekly?) opportunity to do this.  
A: I'll try not to rant.
Necessity of a Transition Course?
The way I see it, you will need a transition course if the following applies:


*

*Your students start out with Calculus;

*Your school mixes math majors with others in Calculus (for size reasons or other).


For instance, at Vassar the typical major starts with linear algebra in the fall followed by multivariate in the Spring. That's already very "proofy" (certainly the way they seem to do it is!) and, as you can check, there is no proofs course on their catalog. I had a somewhat similar experience doing my UG in France.
You need #2, because if you can have dedicated Calculus sections for math majors, then as Pete pointed out, you can take them through a course that will teach them both Calc and proofs, but you wouldn't want to submit the general public to that course.
So to come back to the OP's question, I don't really think there is much of a choice between option 1 and option 2 because which one applies depends only on your public and material circumstances, not really on pedagogical choices.
What I'm really interested in
So the way I see it, if #1 & #2 hold, then you do need that transition, because the first romp through calculus has to be more computational, or you're really short-changing your students, both math-majors and not, at least in a typical course. So at some point, the students will need to transition, i.e. OP's model 1.
Now a related question is how do you help the students transition. And I have yet to teach my institution's proofs course, but I am very skeptical of these. At the very least, I can say that I've seen textbooks that were not promising at all: I like the logic and truth table bits, though where I am this would be covered in Discrete Math, i.e. before the proofs class. But some texts have:
here is a chapter about how to do proofs in linear algebra, here is a chapter about how to do proofs in geometry, etc., somehow emphasizing the differences instead of the commonalities in proofs.
I should mention that  not all textbooks are this bad; this semester, we're using the art of proof that seems a decent book. However, I think it's interesting that none of these books really seem to stand on their own: they are textbooks first and books second, when most of the books in my math library can be picked up and enjoyed whether you're taking a course from them or not.
To me, a proofs course remains a weird animal. I'd much rather ease the transition within a specific topic (e.g. Linear Algebra in my Vassar example). Also, learning how to write proofs is a long process, just like writing in general. The proofs class somehow sends students the message that there's an off-on switch: before this course you don't know how to write proofs, after this course you will; leaving a rather misleading impression.
A: If you should like approach 2, even a little, you should check out chapter 3 of
How to Prove It: A Structured Approach
(Thanks to Amit and Thierry for their comments! This should have been my answer, as the other stuff was mostly my opinion/a defense for suggesting the book.)
