1. Prove: is a solution to the recurrence relation for when and

2. Show that if A and B are sets then

3. Let be a symetric and transitive relation on a set A. Assume for every there exists a with . Prove that R is an equivalence relation.

4. Let G be a graph with vertices and let be distinct vertices on G. Prove that if there is a walk from to , then it has length less than or equal to

Would really appreciate some help with these. Thanks