• DeMorgan's Laws
• Negation of quantifiers
• Defintion of O(), Big-Theta().
• Bound on the n-th Harmonic Number
• Definition of C(n,k)
• Binomial Theorem
• Pascal's Identity
• Definition of transitive relation
• Euler's Formula

Review some proofs by induction, pidgeon-hole proofs, and combinatorial arguements for identites involving C(n,k) such as Theorem 4 on page 333. For practice, you can look at the following problems:

• Page 293, question 27.
• Page 311, question 33c.
• Page 319, question 21.
• Page 325, question 23.
• Page 333, question 21a.
• Page 556, question 43.
• Page 612, question 13.

• How many possible relations r:A->A are there which are equivalence relations with exactly two equivalence classes?
  Answer: (2^|A| /2)-1, since an equivalence relation with exactly two equivalence classes divides the elements of A into two subsets, so each pair of complementary subsets corresponds to an equivalence relation with two classes. We subtract one because the pair of compelementary subsets consisting of all of A and the empty set defines an equivalence relation with only one class.

• Consider the recurrence relation T(n) = T(floor(sqrt(n))) + m, where m is a constant. Give the best O() bound you can on T(n), and prove your result by induction.
  Answer: First we need to figure out what bound to go for. We can write n=2^x, so that n = log₂x. Then the recurrence relation looks like:
  T(x) = T(x/2) + m
  We have seen in other problems that solution to this is O(log(x)), so the solution to the recurrence in terms of n should be O(log(log(n))). So we will prove using strong induction that T(n) is O(log(log(n))).
  Basis step: T(4) is a constant, which is O(log(log(4)))= O(1).
  Induction step: The inductive assumption is that T(i) is O(log(log(i))), for all 4 <= i <= n-1. Using this, we show that T(n) is O(log (log (n))).
  T(n) = T(floor(sqrt(n))) + m <= c log(log(sqrt(n))) + m
  by the inductive assumption, and
  c log(log (sqrt(n))) + m = c log(log(n)) - c + m
  This will be < c log(log(n)) if we choose any c > m. So T(n) is O(log (log (n)) using explict constants k=4 and c>m.