What topics are appropriate for an Introduction to Proofs course which is:
I would say that one of the main things to make sure is that the material covered satisfies two things:
The reason for the first is that this makes it much easier to justify spending a course learning this stuff, and therefore the students will hopefully not think it is a waste of time.
The reason for the second is that many students will get desillutioned if all they are able to prove are statements that are completely obvious, and at the same time, proving something which is "obvious" can in fact be incredibly hard unless you are already very experienced (the students will often end up very confused about which facts they are allowed to use and which ones not).
That the statements should not be too hard to prove when using the right technique and using the definitions seems obvious, as the students will otherwise be stuck not being able to think of the correct "trick", and will end up not getting the proper feeling of what it takes to prove something.
The above then of course begs the question: "Which topics satisfy this", to which my best reply will be from personal experience, having taken a course with these topics myself.
In that course, the curriculum was:
The first two topics are very important to get everyone on the same page when it comes to the notation used, and introducing the various proof techniques fits in well while introducing this notation (since it is related to the rules for how one can manipulate the connectives).
Induction is of course vitally important for all mathematicians to know, and getting introduced to it more formally can hopefully make the students more aware of precisely why and how it works.
Relations, especially the special types covered, are of course something everyone will end up using a lot, and so getting a formal introduction is nice, especially as this is a topic that allows for a huge amount of not quite obvious but not really hard exercises (such as equivalent definitions of being injective or surjective, equivalence relations corresponding to partitions and so on). This topic also allows for a lot of examples, many of which the students will have seen without the formality.
The final topic, construction of the reals, is a little bit different, in that many of the proofs involved will be a lot harder.
But it does introduce some quite nice things to the students, since the construction of something as the set of equivalence classes of something else is done a lot in mathematics (in some sense one might call it the way mathematicians "patch" sets to obtain missing objects, such as in this case obtaining the limits of sequences that should converge but do not, by declaring the sequence itself to represent its limit).
At the same time, this topic will have the students do several epsilon-delta proofs, which is something most students at this level will still need to practice.
The course in question used the book Chapter Zero by Carol Schumacher, which I heartily recommend.
I find that basic inequality proofs are very well recieved.
For instance, given that $x^2 \geq 0$ for $x \in \mathbb R$, prove that $a^2 + b^2 \geq 2ab$ for all $a,b \in \mathbb R$. Bonus points for finding all sets of $a,b$ that satisfy the equality. This is very basic, and requires only some fundamental algebra to sort out.
And from there, there's a wide variety of equalities to prove, that are both important to know, and interesting to discover.
Each problem is different, I think it is best to illustrate proof techniques with a variety of problems. The problems themselves should be simple, easy to understand, perhaps even well known to the audience. I emphasize writing proofs in a schematic way: announce what strategy will be used, and write down the steps, explaining each one. I like Hammack's The book of proof as a guide.
A full course on this is probably nonsense, I'm a firm believer in that you learn stuff only if you use it in real settings, by applying it. Give a short overview at the beginning of the class, use the schemas introduced consistently, and make frequent references.
Some combinatorics: For example the identity $\binom{n}{r} = \binom{n-1 }{r} + \binom{n-1}{r-1}$ can be proven using the formula involving factorials. It can also be proved using combinatorial interpretation. Similarly Vandermonde's identity can be presented in two ways.
