Some comments from Jose

1. When you are trying to prove a recurrence relation, you usually DO NOT use induction in your proof. However, the most common reason for establishing a recurrence relation is that once you have it, you can use it in inductive proofs.
2. When you are dealing with indices and summations you have to be *REALLY careful* to not mess them up. Otherwise, you end up making many silly mistakes.
3. If you are confused whether to multiply or add results in a counting problem, you must review the multiplication and addition principles.
4. In many solutions for problem #4 the answer provided was (at least for large n) bigger than n!, that is, it was bigger than the total number of permutations !!! Try to plug the small values of n into your answers to see if the things you're trying to prove make sense. It is always good to compute small cases by hand and compare the results you get with your general formula.