Question 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.
Question 2: Let n = (abc)7. Show that n ≡ a + b + c (mod 6).
Question 3: Use congruences to prove that 4|32n 1 for all integers n ≥ 0.
Question 4: Let a0, a1, ..... be the sequence recursively defined by a0 = 1, and an = 3 + an-1for n ≥ 1.
a) Compute a1, a2, a3 and a4.
b) Guess a formula for an, n ≥ 0.
c) Use induction to prove that your formula is correct.
Question 5: Define a sequence bn by b0 = 5, b1 = 9, and bn = bn-1 + bn-2 for n ≥ 2.
Use strong induction to prove that bn < 5 . 2n for all n ≥ 1.
Question 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.
Question 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?
Question 8: How many ways can six men and three women form a line if no two women may stand behind each other?