1

A. If |A| = n, |B| = m and |A B| = x, what is |A B|? Briefly justify your answer.

B. Suppose that |S| = n. Use induction to prove |2^S| = 2^|S|. 2^S is the notation for the power set of S.

C. The relation x y if and only if x mod 5 == y mod 5 is an equivalence relation. Use this equivalence relation to partition the set {2, 4, 5, 6, 9, 23, 24, 31, 37} into equivalence classes.

D. How many substrings ab are there in ww^Rw, where w = bbaaba?

E. Use induction on |w| to prove that (w^R)^R = w for all w ^*.