Um livro bem legal é:
How to Prove It: A Structured Approach - Daniel J. Velleman.

Um outro livro muito legal foi publicado pela SBM é:
Um Convite a Matemática - Daniel Cordeiro de Moraes Filho.

Um livro com bons exemplos de provas claras e "charmosas" de resultados básicos é
C. Alsina e R. B. Nelson Charming proofs. Mathematical Association of America, 2010.
