problem 1: Let A be a nonempty set. Define the relation R on the nonempty subsets of A by (X; Y) ε R if and only if X ∩ Y ≠ Φ. Determine whether R is (i) reflexive, (ii) symmetric, (iii) antisymmetric, (iv) transitive.
problem 2: Let n = (abc)_{7}. Show that n ≡ a + b + c (mod 6).
problem 3: Use congruences to prove that 4|3^{2n} 1 for all integers n ≥ 0.
problem 4: Let a_{0}, a_{1}, ..... be the sequence recursively defined by a_{0} = 1, and a_{n} = 3 + a_{n-1}for n ≥ 1.
a) Compute a_{1}, a_{2}, a_{3} and a_{4}.
b) Guess a formula for a_{n}, n ≥ 0.
c) Use induction to prove that your formula is correct.
problem 5: Define a sequence b_{n} by b_{0} = 5, b_{1} = 9, and b_{n }= b_{n-1} + b_{n-2} for n ≥ 2.
Use strong induction to prove that b_{n} < 5 . 2^{n} for all n ≥ 1.
problem 6: Find the number of six-digit positive integers that can be formed using the digits 1, 2, 3, 4, and 5 (each of which may be repeated) if the number must begin with two even digits or with two odd digits.
problem 7: In a collection of 30 di§erent birds, 15 eat worms, 18 eat fruit, and 12 eat seeds. Exactly 8 eat worms and seeds, 8 eat worms and fruit, 7 eat fruit and seeds, and 4 eat all three types. Two birds are selected at random. What is the probability that:
a) both birds eat at least one of these food groups?
b) both eat at least one common food group?
c) both eat all three food types?
problem 8: How many ways can six men and three women form a line if no two women may stand behind each other?