1. Let A and B be finite sets. Given that there exists a bijective function f : A t B we

may conclude that:

(a) |A| < |B|   (b) |A| W |B|   (c) |A| = |B|   (d) |A| ⇤ |B|   (e) |A| > |B|

2. How many numbers are there between 1 and 1000 that are divisible by 15 and 2?

(a) 100

(d) 33

(b) 66

(e) None of the above.

(c) 12

3. The general solution of the recurrence relation xn = 8xn−1 ⌅ 16xn−2 is which one of the following expressions, where A and B are constants:

(a) xn = A4n         (d) xn = A4n + B4n

(b) xn = A2n + B8n

(e) xn = A4n + Bn4n

(c) xn = A2n + Bn8n

4. . . . 20. (There will be 20 multiple choice questions in the real exam.)

Extended Answer Section

There are five questions in this section, some with a number of parts.  Write your answers in the space provided below each part.  You must show your working and give reasons for your answers. If you need more space there are extra pages at the end of the examination paper.

1.  (a) Consider the sets A =  {a,b,c,1, 2, 3}, B  =  {b,c,1, 4, 5}, and C  =  {1, 2, 3, 4, 5}. Write down explicitly a bijection from A / B to B U C, or explain why one does not exist.

(b) Let X,Y be sets and consider functions f  : X → Y  and g  : Y → X .  Suppose that for every y ⌃ Y we have that f(g(y)) = y .  Prove that f is surjective .

(c)  Suppose that A,B, C are sets .  Prove the statement      A / (B U C) = (A / B) ⌥ (A / C) .

(A Venn diagram is not su⇥cient, be explicit about the elements in A , B, and C .)

(c) How many arrangements are there with the W and M together?

3.  (a) Suppose that (an)n⇥1 is a sequence defined by

a1 = 1, a2 = 3 and ak = ak−1 + ak−2  for all k ⇤ 3.

Prove that for all n ⇤ 1, we have

an ⇥ (  ⇥n .

4. and 5. There will be five extended questions in the real exam.