A

You may use one sheet of handwritten notes, but no other sources. The exam consists of five questions, and lasts fifty minutes. Please work all five problems. Please show all work clearly and in reasonable detail. Answers without appropriate supporting work or requested explanations may not receive full credit. No calculators are allowed.

1. (20 points.) Solve the recurrence relation a_n = 4a_n-1 - 4a_n-2 for n ≥ 2, with a₀ = 6, a₁ = 8.
2. (20 points; each part is worth 10 points) The three sets A, B, and C contain 20, 30, and 35 elements respectively.
   1. Find the number of elements in A ∪ B ∪ C if the three sets are pairwise disjoint.
   2. Find the number of elements in A ∪ B ∪ C if there are two elements common to each pair of sets and one element in all three sets.
3. (20 points) In a close election with 101 voters, candidate C received 49 votes and candidate F received 48 votes. There were four votes that were not counted due to problems with the machines, so these votes are going to be recounted by hand. Assume that these four votes are independent and for each of them the probability that they vote for candidate C is 0.4 and for candidate F is 0.6. What is the probability that candidate F wins the election? (Express your answer in factorials and/or powers of numbers.)
4. (20 points) Let G = (V,E) be a connected graph. Let n = |V |, the number of vertices in V . Assume the number of edges is |E| = n- 1. Prove that G must have at least one vertex of degree equal to one. (Hint: use the handshaking theorem.)
5. (20 points.) Let G = (V,E) be a connected graph. Let n = |V |, the number of vertices in V . Assume the number of edges is |E| = n - 1. Prove that G contains no cycles. (Hint: use induction. You can assume the result of Question 4 is true.)