Which do you recommend for learning how to write proofs — How to Prove it by Velleman, or How to Solve it by Polya?

Solution 1:

Velleman's How to Prove it is quite a bit more relevant to your needs. It is organized like a conventional text, and pays a lot of attention to proof writing.

Polya's book focuses on problem-solving. One can view it as a better book, certainly a historically far more important book. But it focuses on how one finds the idea that will crack a concrete problem.

There is quite a bit of material in Velleman that is useful for writing proofs in linear algebra, in particular on how to proceed from definitions. There is none of that in Polya. There is also essentially nothing in Polya on basic analysis. Polya beautifully accomplishes his aims: they just happen to be different from what you said you wanted.

Solution 2:

The Polya is more advanced than I think you are looking for. It is a well-known classic, but assumes the reader already knows how to write proofs.

I haven't seen it, but the Velleman should be good for you. Another one I have seen is by Solow: How to Read and Do Proofs