1. Given below are several pairs of functions f(n) and g(n). For each pair, . Show work. For some of these, you may need to use L'Hospital's rule. (20 points)
(a) f(n) = 15n2 and g(n) = 5. (b) f(n) = 2n and g(n) = n2.
(c) f(n) = n ln n and g(n) = 17n2 + 4. (Note that “ln" denotes the natural logarithm.) (d) f(n) = 3n and g(n) = 2n.
2. (a) Use induction on n to prove that for all integers n >= 0, the value 4n + 1 is not divisible by 3. (20 points)
(b) Consider the infinite sequence of integers f0, f1, f2, …, defined by f0 = 1, f1 = 2 and
fn = fn-1 + fn-2 for all n >= 2. Use induction on n to prove that for all n >= 1. (20 points)
3. Let A = {x; y; z; w} and let B = {1; 2; 3}. Determine the number of functions from A to B that are neither one-to-one nor map y to 3. Show work. (20 points) Hint: Use the principle of inclusion-exclusion.
4. Let A = {x1; x2; …; x10} be a set of 10 positive integers, not necessarily distinct, such that xi <= 10, 1 <= i <= 10. Prove that there are at least two different 5-element subsets S1 and S2 of A such that the sum of the elements in S1 is equal to the sum of the elements in S2.
(20 points)
Hint: Use the pigeonhole principle.
