Exam 3 Exam 3                              Friday, May 11, 2001

NAME:

Student Number:------            No.----           Marks ----

Instructions:

1. You have 50 minutes for this exam.

2. This exam contains 3 questions and has a total of 100 marks.

1.    (40 Marks)    Use mathematical induction to show that for each n Î Z+,

 nå i = 1 1(2i-1)(2i+1) = n2n+1 .
(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,

 kå i = 1 1(2i-1)(2i+1) = k2k+1
(2)

We prove that when n = k+1, (1) holds, that is,

 k+1å i = 1 1(2i-1)(2i+1) = k+12(k+1)+1 .
(3)

In fact, by (2), we have

 k+1å i = 1 1(2i-1)(2i+1)
 =
 kå i = 1 1(2i-1)(2i+1) + 1(2(k+1)-1)(2(k+1)+1)
 =
 k2k+1 + 1(2(k+1)-1)(2(k+1)+1)
 =
 k(2k+3)+1(2k+1)(2k+3)
 =
 2k2+3k+1(2k+1)(2k+3)
 =
 (2k+1)(k+1)(2k+1)(2k+3)
 =
 k+12(k+1)+1 .

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.

File translated from TEX by TTH, version 2.79.
On 12 May 2001, 09:29.