I now realize that a big part of higher mathematics is proof construction, and it is an area I would like to get familiar with.
I have found the book ‘how to prove it’ by Velleman, but am wondering if anyone has any other suggestions for proof.
In terms of difficulty I am looking for a book of relative ease as I am new to proof. Any suggestions would be appreciated, thanks.
Here is a list of freely available books I know, but since I've personally learnt proofs before most of them were written, I am no good judge of their quality as proof tutorials:
Eric Lehman, F Thomson Leighton, Albert R Meyer, Mathematics for Computer Science. Part I is specifically about proofs, and parts II and III should provide good practice. It's written for MIT students, so it might be a bit fast-going, but it's written in an enjoyable lively style (most math books either avoid or fail at jokes; this one is an exception).
Martin V. Day, An Introduction to Proofs and the Mathematical Vernacular (archive.org mirror). Big upside (to me) is that it does determinants in detail. A downside is that it mis-defines polynomials as functions.
Daniel J. Velleman, How to prove it, 2nd edition 2006. This seems to be slow and systematic, but (as a consequence) doesn't get far enough to prove anything really exciting. This is, of course, a common problem with introductions to proofs, particularly when they are written for 1-semester courses.
Richard Hammack, Book of proof. Roughly same level as Velleman, from its look.
Clive Newstead, An Infinite Descent into Pure Mathematics. Still a work in progress. This goes deeper than most other comparable texts into combinatorics (e.g., the "path-dependent product rule" for counting is formalized and proven!).
Paolo Aluffi, Introduction to Advanced Mathematics. These are lecture notes (though they seem reasonably polished), and also suffer from the "not getting anywhere too interesting" syndrome (see Velleman), but Aluffi is known for enjoyable writing.
James Aspnes, Notes on Discrete Mathematics. This is written from a TCS point of view (e.g., page 41 is a table of the rules of natural deduction), but it covers the usual ground along with some graph theory and enumerative combinatorics. Aspnes writes well (here are notes on introductory programming, C++ and Linux).
Matthias Beck and Ross Geoghegan, The Art of Proof: Basic Training For Deeper Mathematics.
Alistair Savage, MAT1362 Mathematical reasoning and proofs. These notes are written for a course that follows Beck and Geoghegan, so can be regarded as an expanded version of parts of the latter, including proofs that are omitted from the latter. See Savage's teaching page for more notes.
Ted Sundstrom, Mathematical Reasoning: Writing and Proof.
Franco Vivaldi, Mathematical writing for undergraduate students. This is likely a draft of his 2014 book.
These are just the ones I have found in my personal library and freely available on the internet; if I had listed the paywalled ones, this post would be again as long. As I said, I have not actually learned proofs myself from any of these, so all I can offer are quick judgments based on leafing through.