We discussed the handshake problem (c.f p.50 and 60 in your textbook) as yet another example of a proof by induction. I tried to explain why p implies not q was not the negation of p implies q. Since my explanation did not seem too satisfactory, I will try to find the ultimate explanation for next time.
Here are some more problems on induction: 3.31/3.32, 3.33, 3.39, 3.40, Proposition 3.16 and Problem 3.49. A lot of those problems require formulating a guess before proving it by induction, which should make them more challenging than those you have experienced so far.