Student Number:_{} No._{} Marks _{}
1. You have 50 minutes for this exam.
2. This exam contains 3 questions and has a total of 100 marks.
3. Show all of your work. Your work must justify the answer that you
give.
1. (40 Marks) Use mathematical induction to show that for each n Î Z^{+},
 (1) 
Proof: When n = 1, LHS = 1/3 and RHS = 1/(2+1) = 1/3. Hence, (1) holds when n = 1.
Assume that (1) holds when n = k, that is,
 (2) 
We prove that when n = k+1, (1) holds, that is,
 (3) 
In fact, by (2), we have

Hence, (3) holds when n = k+1. By induction, (1)
holds for each n Î Z^{+}.
2. (30 Marks) How many ways are there to choose 6 items from 10 distinct items when
a) the items in the choices are unordered and repetition is not allowed?
b) the items in the choices are ordered and repetition is not allowed?
Solution. a) C(10,6) = [10!/6!4!] = 210.
b) P(10,6) = 10×9×8×7×6×5 = 151200.
3. (30 Marks) For each of the following relation on the set {1,2,3,4}, decide whether it is reflexive, whether it is symmetric, whether it is transitive.
a) {(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)}.
b) {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}.
c) {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}.
Solution. a) Transitive
b) reflexive, symmetric and transitive
(c) None of these properties.