PROBLEM 4 (10 points)
Suppose T(0) = 0 and for all n > 0, T(n+1) = rT(n) + a, where r and a are constants. Prove by
induction that for all n > 0:
PROBLEM 5 (5+5 points)
(A) How many different terms of the form xxxxx where i > 3, j 2, k 1, are equal to x13?
(B) Arrange the following in Big-O order, so if f comes before g, then f is O(g).
4n², log3(n), log2(n!), nn, :1. 3n, n log2(n), 2n+1, 17, n!, 22n
PROBLEM 6 (5 points)
Does this series converge or diverge? Explain why.
PROBLEM 7 (2+2+2+2 points)
Determine which of the following properties are equivalence relations. If the relation is an equiv-
alence relation, describe the equivalence classes. Otherwise, explain why it is not an equivalence
(A) The relation R on Z where aRb iff a < b
(B) The relation R on pairs of real numbers where iff y = y2.
For each of the following, state whether the set is finite, countably infinite, or uncountably infinite.
(C) The set of numbers of the form a + bV2 where a, b € N.
(D) The powerset of the set of all sentences that contain fewer than 10 words. (A word is something
listed in some standard dictionary.)
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.