Reddit reviews Walk Through Combinatorics, A: An Introduction to Enumeration and Graph Theory (Third Edition)

For proofs in general, I like D'Angelo and West's Mathematical Thinking. http://www.amazon.com/Mathematical-Thinking-Problem-Solving-Proofs-Edition/dp/0130144126

For discrete math, especially combinatorics, I loved Miklos Bona's A Walk Through Combinatorics. http://www.amazon.com/Walk-Through-Combinatorics-Introduction-Enumeration/dp/9814335231/

For induction proofs, you check your base case, assume the induction hypothesis (true for k), and then check k+1.

You should be able to manipulate the k+1 term into something involving the k term, and that will then lead to the k+1 conclusion.

Example For all n >= 4, 2^(n) < n!

Base case: n = 4. 2^(4) = 16 < 24 = 4!

IH: Assume true for some k >= 4.

Then 2^(k+1) = 2*2^(k)

2*2^(k) < 2*k! (Induction Hypothesis used here)

2*k! < (k+1)k! (k > 3, so k+1 > 2)

(k+1)k! = (k+1)! (definition of factorial)

I would recommend these, as well as

http://www.math.upenn.edu/~wilf/DownldGF.html

http://www.amazon.com/Walk-Through-Combinatorics-Introduction-Enumeration/dp/9814335231

http://www.amazon.com/Introduction-Graph-Theory-Douglas-West/dp/0130144002/