Solutions to Assignment 01 Semester 1.
QUESTION 1
(a) For each of the following statements give the converse, the contrapositive and the
negation of the statement.
(i) When I go shopping, then I take plastic bags.
converse: I take plastic bags when I go shopping.
contrapositive: I don’t take plastic bag when I am not going shopping.
negation: When I go shopping, I never take plastic bags with me.
(ii) x 2= B implies x 2 X and x 2 Y
converse: If x 2 X and x 2 Y then x 2 = B:
contrapositive: If x 2 = X or x 2= Y then x 2 B:
negation: If x 2 = B then either x 2
= X or x 2
= Y:
(iii) If jxj < 3; then x 2 A \ B
converse: If x 2 A \ B then jxj < 3:
contrapositive: If x 2 A \ B then jxj 3:
negation: If jxj < 3; then x 2 = A \ B:
(iv) 0 < jx + 2j < implies jf (x) Lj < "
converse: If jf (x) Lj < " then 0 < jx + 2j < :
contrapositive: If jf (x) Lj " then jx + 2j where x 6= 2:
negation: If 0 < jx + 2j < then jf (x) Lj ":
(b) There exists b 2 B such that for each x 2 A; x b:
Negation: For every b 2 B there exists an x 2 A such that x > b:
(c) Use a proof by contradiction to establish the following:
If a positive whole number n can be expresses p as n1 n2 , where n1 2 and n2 2;then
at least one of the set fn1 , n2 g is less than n:
Proof:
Suppose n = n1 n2 with n1 2 and n2 2 and n1 6= n2 :
NB
This next assumption is the most important p part of p
your proof. p
Assume that neither of n1 nor n2 is less than n; i.e. n1 n and n2 n:( )
Now let p
n1 = n + 1
and p
n2 = n+ 1
1
, where both
1 0 and 2 0, 1 6= 2 (since n1 6= n2 ).
At least one of 1 and 2 is strictly larger than 0. Suppose that 1 > 0:
Then
n = n1 n2
p p
= ( n + 1 )( n + 2 )
p
= n + n( 1 + 2 ) + 1 2
> n
since ( 1 + 2 ) > 0:
This is surely a contradiction and thus our assumption ( ) is wrong.
Thus pif n = n1 n2 , where n1 2 and n2 2;then at least one of the set fn1 , n2 g is less
than n:
QUESTION 2
(a) Prove by induction that
3n 2n2 + 1 for all n 2 N
Proof:
If n = 1; then LHS = 3 and the RHS = 2 + 1 = 3
Hence 3n 2n2 + 1 is true for n = 1:
Suppose true for n = k; k 1:Then
3k 2k 2 + 1 (*)
Now we need to prove the equation is also true for n = k + 1 using (*) i.e. we need to prove
.
3k+1 2(k + 1)2 + 1
LHS = 3k+1 = 3(3k )
3(2k 2 + 1) = 6k 2 + 3 using (* )
RHS = 2(k + 1)2 + 1
= 2k 2 + 4k + 2 + 1
= 2k 2 + 4k + 3
2k 2 + 4k 2 + 3
= 6k 2 + 3
Thus we have porved the RHS LHS i.e.
3k+1 2(k + 1)2 + 1
(b) 8 2x 1
>
< if x 6= 1
g (x) = x+1
>
:
2 if x = 1
2
QUESTION 1
(a) For each of the following statements give the converse, the contrapositive and the
negation of the statement.
(i) When I go shopping, then I take plastic bags.
converse: I take plastic bags when I go shopping.
contrapositive: I don’t take plastic bag when I am not going shopping.
negation: When I go shopping, I never take plastic bags with me.
(ii) x 2= B implies x 2 X and x 2 Y
converse: If x 2 X and x 2 Y then x 2 = B:
contrapositive: If x 2 = X or x 2= Y then x 2 B:
negation: If x 2 = B then either x 2
= X or x 2
= Y:
(iii) If jxj < 3; then x 2 A \ B
converse: If x 2 A \ B then jxj < 3:
contrapositive: If x 2 A \ B then jxj 3:
negation: If jxj < 3; then x 2 = A \ B:
(iv) 0 < jx + 2j < implies jf (x) Lj < "
converse: If jf (x) Lj < " then 0 < jx + 2j < :
contrapositive: If jf (x) Lj " then jx + 2j where x 6= 2:
negation: If 0 < jx + 2j < then jf (x) Lj ":
(b) There exists b 2 B such that for each x 2 A; x b:
Negation: For every b 2 B there exists an x 2 A such that x > b:
(c) Use a proof by contradiction to establish the following:
If a positive whole number n can be expresses p as n1 n2 , where n1 2 and n2 2;then
at least one of the set fn1 , n2 g is less than n:
Proof:
Suppose n = n1 n2 with n1 2 and n2 2 and n1 6= n2 :
NB
This next assumption is the most important p part of p
your proof. p
Assume that neither of n1 nor n2 is less than n; i.e. n1 n and n2 n:( )
Now let p
n1 = n + 1
and p
n2 = n+ 1
1
, where both
1 0 and 2 0, 1 6= 2 (since n1 6= n2 ).
At least one of 1 and 2 is strictly larger than 0. Suppose that 1 > 0:
Then
n = n1 n2
p p
= ( n + 1 )( n + 2 )
p
= n + n( 1 + 2 ) + 1 2
> n
since ( 1 + 2 ) > 0:
This is surely a contradiction and thus our assumption ( ) is wrong.
Thus pif n = n1 n2 , where n1 2 and n2 2;then at least one of the set fn1 , n2 g is less
than n:
QUESTION 2
(a) Prove by induction that
3n 2n2 + 1 for all n 2 N
Proof:
If n = 1; then LHS = 3 and the RHS = 2 + 1 = 3
Hence 3n 2n2 + 1 is true for n = 1:
Suppose true for n = k; k 1:Then
3k 2k 2 + 1 (*)
Now we need to prove the equation is also true for n = k + 1 using (*) i.e. we need to prove
.
3k+1 2(k + 1)2 + 1
LHS = 3k+1 = 3(3k )
3(2k 2 + 1) = 6k 2 + 3 using (* )
RHS = 2(k + 1)2 + 1
= 2k 2 + 4k + 2 + 1
= 2k 2 + 4k + 3
2k 2 + 4k 2 + 3
= 6k 2 + 3
Thus we have porved the RHS LHS i.e.
3k+1 2(k + 1)2 + 1
(b) 8 2x 1
>
< if x 6= 1
g (x) = x+1
>
:
2 if x = 1
2
