1.  (a) Use proof by cases to show that |x−1|+|x+5| ≥ 6 for every real number x.   

(b) Consider the following statement.

Let a,b,c,d  be positive  integers such that a mod b = 0 and c mod d  = 0. Then (a + c) mod (b + d) = 0.

Decide if the statement is true or false. If it is true, prove it.

If it is false, give a counterexample.                         

2.  (a) Solve the recurrence relation

an  = 8an − 1 + 9an −2

with initial conditions a0  = 1 and a1  = 4.

(b) Compute the value of a3  in two different ways: the recursive definition,

and the closed formula obtained in (a).

3.  On the set A = {2, 3, 4, 5, 6, 8, 9, 12, 15, 18}, consider the binary relation R. R = {(i,j)  |  i divides j}

This relation is a partial order on A. (You do NOT need to prove this.)

Answer the following:

(a) Draw a Hasse diagram of this partial order.

(b) List all maximal elements of this partial order.

(c) List all minimal elements of this partial order.

(d) List the greatest element of this partial order, if it exists; otherwise, briefly explain why it does not exist.

4. Does there exist a simple connected undirected graph with eight vertices having degrees 1, 1, 1, 2, 3, 4, 5, 7? You must justify your answer.

5.  (a) Let r ∈ P, and let A be any subset of {1, 2, . . . 2r} with |A| = r + 1. Prove that there are two distinct elements of A that sum to 2r + 1.

(b) Assume r = 3. Suppose |A| = r instead. Show that the claim in (a) is no longer always true.

6.  Consider the set A of all strings of length 12 defined over the alphabet {5,y,$}.

(a) How many strings are there in A? You must justify your answer.

(b) B = {w ∈ A: 5 and y each occur exactly once in w}.

What is |B|? You must justify your answer.

(c) How many strings in A contain precisely two y which are not adjacent and no 5? You must justify your answer.

7. Let X denote the subsets of {1, . . . , 5}, let Y := {y ∈ N : 0 ≤ y ≤ 20}.

Define f : X '−→ Y by f(S) = |S| where S ∈ X .

Define g : Y '−→ N by g(y) = 2y for y ∈ Y .

(a) Is f onto? Is g onto?

(b) Decide whether or not f 。g is defined?

(c) Decide whether or not g 。f is one-to-one. You must justify your answers.

8.  (a) How many 6-element subsets of {1, . . . , 25} have largest element 20?