MAT2612 Assignment 1 memo

COMPULSORY ASSIGNMENT FOR EXAMINATION ADMISSION

ASSIGNMENT 01
Total Marks: 100
Memorandum

ONLY FOR YEAR MODULE

All questions will be marked.

DO NOT USE A CALCULATOR TO OBTAIN YOUR ANSWERS-WHERE APPLICABLE, LEAVE
YOUR ANSWERS IN TERMS OF FACTORIALS, n Cr AND n Pr .




Question 1: 10 Marks

Suppose  
    1 0
0 1 0 0 1 1
A= ,B = and C = 1 0 .
1 1 0 0 0 1
0 1
Compute the following:



(1.1) A + B, (2)
Solution      
0 1 0 0 1 1 0 2 1
A+B = + = .
1 1 0 0 0 1 1 1 1



(1.2) BC, (2)
Solution  
  1 0  
0 1 1  1 1
BC = 1 0 =
 .
0 0 1 0 1
0 1



(1.3) A ∨ B, (2)
Solution      
0 1 0 0 1 1 0 1 1
A∨B = ∨ = .
1 1 0 0 0 1 1 1 1




2

, /


(1.4) A ∧ B, (2)
Solution      
0 1 0 0 1 1 0 1 0
A∧B = ∧ = .
1 1 0 0 0 1 0 0 0



(1.5) B ⊙ C. (2)
Solution  
 1 0  
0 1 1 1 1
B⊙C = ⊙ 1 0 =
  .
0 0 1 0 1
0 1
See the section on Boolean Matrix Operations in Section 1.5 of KBR.




Question 2: 20 Marks

Use Mathematical induction to show that:

(2.1) 5n − 1 is divisible by 4 for all n ∈ N; n ≥ 1. (10)
Solution
Let P(n) be the statement
5n − 1 is divisible by 4.
Basis step:
Let n = 1. Then 5n − 1 = 4, which is clearly divisible by 4. Thus P(n) is true for n = 1.

Induction hypothesis:
Assume P(k ) is true for some k ≥ 1, k ∈ N, i.e.

5k − 1 is divisible by 4.

To prove:
We neet to show that Pk + 1 is true, i.e.

5k +1 − 1 is divisible by 4.

Proof:


5k+1 − 1 = 5(5k ) − 1,
= (4 + 1)5k − 1,
= 4 · 5k + 5k − 1.

Now, 4 · 5k is divisible by 4, and by the induction hypothesis, 5k − 1 is divisible by 4. Hence the sum
4 · 5k + 5k − 1, i.e., 5k+1 − 1 is divisible by 4. Thus P(k + 1) is true.
It follows that by the principle of Mathematical induction that 5n −1 is divisible by 4 for all n ∈ N; n ≥ 1.


3