Math 231 Winter 2020 Final Exam Study Guide Homework Solutions

This document presents solutions to a discrete mathematics homework assignment for a Math 231 course, likely at the university level, focusing on topics covered in chapters 1 through 5. The solutions cover a wide range of problems including set theory, combinatorics, circular arrangements, perm...Read More

Running head: MATHEMATICS 1
Discrete Mathematics
Name
Institution

MATHEMATICS 2
Solutions
Question 1
Let A, B, and C be sets of integers between 1 and 100000(inclusive) which are divisible by 31,
607, and 1901 respectively. As a result, we want to find;
( AUBUC )C
= | AUBUC| = | A| + |B| + |C | -( AnB ) - ( AnC ) -( AnBnC )
Where;
| A| = 100,000
31 = 3225
|B| = 100,000
607 = 164
|C | = 100,000
1901 = 52
( AnB ) = 100,000
18817 =5
( AnC ) = 100,000
58931 =1
|AUBUC| = 3225+164+52-5-1-2
= 96563
Question 2
Using the formula of circular arrangement of n-objects i.e. (n-1)!

MATHEMATICS 3
9 women will be (9-1)! = 8!, r =6, thus;
P (n,r) = n!
(n−r )! = 9 !
3 ! = 60480
=40320*60480
=2438553600 ways
Question 3
The main objective is to find the numbers of ways of different seating arrangements
=( 16
10 )
Circular arrangement for n-objects will therefore be;
(n-1)!
=(10-1)!
Remaining six people to be arranged on the six seats i.e. (6-1)!
Using the rule of product, we get;
(16
10 ) *9!*5! Ways of seating
Question 4
IIIIMPPSSSS
n=11
I=4, M =1, P=2, and S =4

MATHEMATICS 4
a) = 11!
4 !∗2 !∗4 ! 1 ! = 34650
b) Since I= 4, then n=8 we get;
= 8 !
1!∗1 !∗2!∗4 ! = 840
c) n=5
= 5!
2! = 60 words
d) = 11 !
4 ! 4 ! 2 ! = 34650 = = 1
34650 = 0.0002886
Question 5
We use two ways to determine the number of times the statement counted and executed i.e.
(n+3−1
3 ) = (n+ 2
3 ) times (i+1
2 ) executions of the I, j thus;
( n+2 ) ( n+1 ) n
3 =∑
i=1
n
( i+1
2 )
∑
i=1
n
i = ( n+1 ) n
2
∑
i=1
n
i2= ( n+2 ) ( n+1 ) n
3 - ( n+1 ) n
2
= ( n+1 ) n
6 (2n+1)
( n+ 2
3 )= ∑
i=1
n
( i+1
2 )

MATHEMATICS 5
= ( n+ 2 ) !
3! ( n−1 ) !
( n+2 ) ( n+1 ) (n)
6
= ( 2
2 ) + ( 3
2 ) +-------+ ( n+1
2 )
= ½ (2+6+12+------ (n+1)(n))
= ( n+2 ) ( n+1 ) (n)
6
=1/2 ∑
i=1
n
(i+1 )i
Question 6
X1+ X2+ X3+ X4+ X5+ X6+ X7+ X8+ X9= 27
= X1-1+ X2-1+ X3-1+ X4-1+ X5-1+ X6-1+ X7-1+ X8-1+ X9-1=18
=Consider a= X1-1, b= X2-1, c= X3-1, --------, i= X9-1
=a+b+c+ --------------+i =18
=We therefore know that the number of the solution of the first equation where x1 to x9 cannot
be zero thus equation 2 also cannot be zero. As a result, using the fictious partition method;
(n+ p−1
p−1 ) = (18+9−1
9−1 ) where n=18 and p =9
¿ ( 26
8 ) = 26 !
8 !(26−8)!

MATHEMATICS 6
=1562275
Question 7
X1+ X2+ X3+ X4+ X5+ X6+ X7=23
(n+ p−1
p−1 ) = (23+7−1
7−1 ) where n=23 and p =7
¿ ( 26
8 ) = 23 !
6 !(26−4 )!
=10925460
Question 8
∑
j=0
n
(n
j )2j = 3n
By induction, the statement is true when n =0, thus checking on the Left hand side and Right
hand side, we get;
∑
j=0
n
(0
0 )20 =30
This is true since the LHS and the RHS are equal thus holding the claim true to the statement.
∑
j=0
k +1
(k +1
j )20 =3k+1
=3 thus showing that the LHS and the RHS are equal leading to approve of the theorem.
Question 9
A, B, C є U

MATHEMATICS 7
(A-B) є C ≅ (A-C) є B
Let x є (A-B)n C then x єA-B and x єC by definition
In particular, x є (A-C) n B
Question 10
(A n B) u C = An (B u C) ≅ c є A
Let x є (A n B) U C then x є A n B, and that (A n B) U C = A n (B u C) = C є A since x є A and
x є C
Question 11
a) A∆ B =B ∆ A
Let x є B and x є A thus x є (A u B) showing that (A-B) u (B-A) will have A∆ B = B ∆ A
b) A ∆ A’ = U
Let x є A and also since A and A’ є U then A ∆ A’ = U
c) A ∆ U = A’
Let x є A but since we know that A є U and A’ є U then A and A’ є U thus A ∆ U = A’
d) A∆ ∅ =A
Let x є and given that ∅ is null set, then x є A but empty set will not have anything. As a
result,
A∆ ∅ =A
Question 12
( n+ 2
r ) = (n
r ) + 2 ( n
r −1 ) + ( n
r −2 )

MATHEMATICS 8
From the above given combination, the left hand side counts the number of bit strings of the
length n+2 with r ones. The right hand side counts for the same string according to the cases but
depending on the position of the right hand side. As a result, it must be in one of the positions r,
r-1, or n+2. However, if it is in the position t, then r of the t+1 position will hold on the right
hand side to a value equal to 1. A s result, the number of the bit strings where the right hand side
is 1 is in the position t if t-1 where the rightness also holds to 1 at a point where k =t-1. It
therefore follows the rule of the summation from the combination point of view.
Question 13
a) 2017
2017 (base 10) = base 2: 11111100001
2017 (base 10) = base 8: 3741
2017 (base 10) = base 16: 7e1
b) 2018
2018 (base 10) = base 2: 11111100110
2018 (base 10) = base 8: 3742
2018 (base 10) = base 16: 7e2
c) 2019
2019 (base 10) = base 2: 11111100011
2019 (base 10) = base 8: 3743

MATHEMATICS 9
2019 (base 10) = base 16: 7e3
d) 2020
2020 (base 10) = base 2: 11111100011
2020 (base 10) = base 8: 11111100100
2020 (base 10) = base 16: 7e4
Question 14
a) n = apbq for p and q where the powers are included and one
(p+1)
b) n = zpn
n+1 positive integers
c) (p+1) (q+1)
=(p+1)(q+1) = 6 factors
d) Let n =pn*qm where p and q are prime factors, thus positive divisors will be (n+1)(m+1)
e) 34.11 = 4+1 = 5
f) 23.54.73 = (3+4)(3+3)(4+3) = 756
Question 15
a) C(p,r) is a multiple of p
Using Fermat little theorem;
rp= r mode p
rp-1 =mod p = rp-1-1 thus a multiple of p

MATHEMATICS 10
b) If np-n is divisible of p
This can be shown by stating that;
Using the Fermat little theorem, we say that if p is a prime number, then for any positive integer,
n we will have np =n mod p
Question 16
nєZ+, n = rk.10k +ro
2=-1 (mod 3)=10k≡ (-1)k (mod 3) for all k>0
Using the base 10, we will have;
n= rk.10k +……..+r1.10 +r0 which is not equal to zero
Therefore;
3|n=n≡ mod 3
rk(-1)k+ rk-1(-1)k-1+ ………..+r1+r0 ≡0 (mod 3)
Question 17
7|n if and only if 7| n−ro
10 -2ro
If n is an integer, then the unit digit of 7n is 7 if and only if n is odd and 6 is an even number. If
we say that n=1 and ro is 7 respectively, then the final value of the 7|n if and only if 7| n−ro
10 -
2ro will given integer that proves that n>0 thus holding the inequality true.
Question 18

MATHEMATICS 11
Since (a,b) =d, we know that there are x,y є Z such that ax1 +by1 =d, then ( a
d )x1 +( b
d )y1 and a
d ,
and b
d is in Z. As a result, we say that ( a
d , b
d ¿=1 because if we suppose that it is true, then it will
be ( a
d , b
d ¿= ∂>1. From the relationship given, since ∂ divide the LHS, then equation ( a
d )x1 +
( b
d )y1 holds for ( a
d , b
d ¿= ∂>1
Question 19
a,b є Z+ and d =gcd (a,b).
By hypothesis, there exist integers m, n which are in Z such that d = am+bn
However, if c divides both a and b, then by Fermat little theorem, c will also divide d by the
same application thus d=gcd (a,b) and d2 is therefore a divisible of ab
Question 20
2020x+2019y=1
By the Euclidian Algorithm, 2020.1+2019.1=1
Subtracting 2019 by 1, we get 2019
(2019.-1). 2019. (2020.1+2019.1) thus, x=1, and y=-1
Question 21
2020x+1848y=16
By the Euclidian Algorithm,
2020.1+1848.1=172

MATHEMATICS 12
Subtracting 1848 by 172, we get 10 times
(1848.-1). 10. (2020.1+1848.1)
Subtracting 172 by 128, we get it to be once
Thus x=10, y=-33
Question 22
a
7 + b
12 = 1
84
12a+7b =84
By the Euclidian Algorithm,
12.1+7.1 =5
Subtracting 7 by 5, we get 1
(12.1)-1(12.1+7.1)
12.-1(12.1+7.1)
12.-1 +7.3=9
Subtract 5 by 9 we get 1, then;
(12.1 +7.-1) -1 (12.-1+7.3) showing that a=4 and b=-6
Question 23
The function will be;
20x+50y=1020

MATHEMATICS 13
If we say that a,b, c are in Z then the equation will be in the form;
Ax+by =c ith gcd(a,b)|c
Using the Euclidean theorem;
50=2.20+10
20=10.2+0
gcd (20,50) = 10
gcd (20,50)=10|1020 and 20x+50y =1020
gcd(20,50)=10=50.1-2.20. As a result, x=11 or 6 and y=16 or 18
Question 24
a) (AxB) n (BxA) = (AnB) x (AnB)
Using the distributive law,
AB nBA = (AnB) x (AnB)
b) (AxB) U (BxA) C (AnB) x (AnB)
Using the distributive law,
AB UBA C (AnB) U (AnB)
c) Assuming that A and B are in C, then C=0,1,2,3,4,5
And A =(1,2), and B= (2,3,4), then AUB =2 which proves the relationship as 2U2 which
are all found in the major set, C
Question 25
a) f(x) =x +7

MATHEMATICS 14
f(x1)= f(x2) = x1=x2
f(x1) =f(x2) =x1+7=x2+7=x1=x2 thus showing that the function is one to one due to
same results
b) f(x) =-x+5
f(x1)= f(x2) = x1=x2
f(x1) =f(x2) = -x1+5= -x2+5=x1=x2 thus showing that the function is one to one due to
same results
c) f(x) = 2x-3
f(x1)= f(x2) = x1=x2
f(x1) =f(x2) =2x1-3=x2-3= x1=x2 thus showing that the function is one to one due to
same results
d) f(x) =x2
x1=2, and x2 = -2 thus f(x1) = 4 and f(x2)= 4 but x1 is not equal to x2 thus it is onto
function with a range R : {0,1,4.9,16…….}
e) f(x) = x3
When x1=2, it will give f(x1)= 8, and x2=-2, f(x2) -8 where x1 is not equal to x1 thus
producing onto function with a range, R:{0,2,3…..}
f) f(x) = x2-3
g) If x1= 2, then f(x1) =1 and x2, then f(x2)= 1 showing that f(x) = x2-3 is one to one
Question 26
a) If f:R which transforms to R, then;
f(x)= x+7=y
x=y-7

MATHEMATICS 15
f(y1)= f(y2) = y1=y2
f(y1) =f(y2) =y1-7=y2-7=y1=y2 thus showing that the function is one to one due to same
results
b) f(x) = -x+5
x=-y +5
f(y1)= f(y2) = y1=y2
f(y1) =f(y2) = -y1+5= -y2+5=y1=y2 thus showing that the function is one to one due to
same
c) f(x) = 2x-3
x= 1/2y +3/2
f(y1)= f(y2) = y1=y2
f(y1) =f(y2) =1/2y1+3/2=1/2y2+3/2=y1=y2 thus showing that the function is one to one
due to same
d) f(x)= x2, x=y1/2 showing that there is no x in R that gives f(x)=x2=-1 as a result of the onto
function. The range will therefore be R : {0,1,4.9,16…….}
e) f(x) = x3
x=y1/3
When y1=2, it will give f(y1)= 2/3, and y2=-2, f(y2) =-2/3 where y1 is not equal to y1
thus producing onto function with a range, R:{0,2,3…..}
f) f(x) = x3-3
x=(y+3)1/3,
When y1=2, it will give f(y1)= 5/3, and y2=-2, f(y2) =1/3 thus one to one function
Question 27

MATHEMATICS 16
a) f:A to B injective function with will be 6 functions
b) f:A to B injective function with will be;
f{[a1, b1]………[a4,b4]} thus 6 functions
c) There are four onto functions i.e. f{[a1, b1]………[a4,b4]}
d) One to one functions from B to A will be given as follows;
f{[b1, a1]………[b4,a4],[b3,a5],[b4,a6]} thus five functions
e) There are four ways
f) There are five ways
Question 28
a) There are 6 ways
b) There are 5 ways
c) There are 5 ways
d) There are 6 ways
Question 29
∑
j=0
n
(−1)j
( m
j )(m-j)n = 0
By induction;
If n=1, then ∑
j=0
n
(−1)0
( 1
0 )(1-0)0 = 0
This is true if and only if the left and right hand sides are equal
Question 30

MATHEMATICS 17
∑
j=0
n
(−1)j
( n
j )(n-j)n=n!
By induction n=1 thus,
∑
j=0
n
(−1)0
( 1
0 )(1-01n=1!
Proving the theorem that the left and right hand side are equal
Question 31
7 !
5! 1 !1 ! =42
7 !
4 ! 3 ! = 35
Total = 42+35 = 77 umbers
Question 32
If f is not injective then x1 is not equal to x2 such that;
f(x1) =f(x2) thus f(A)=f(A)\x1
Hence;
|f(A)\= |f(A)\{x1} which is less or equal to|A|\x1=|A|-1<|A|
It therefore shows that;
F injective =\f(A)=|A|
f(A) C B

MATHEMATICS 18
f surjective = f(A) =B = |f (A)|=|B| since |A|=|B|
Problem Set 2
Question 1
∑
i=1
2 n
i = ∑
i=1
2 n
i2
By induction, when n=1, then;
∑
i=1
2
i2 and the same is on both right and left hand side thus proving that the theorem is true
∑
i=1
2
i2= ∑
i=1
2(k +1)
i2 showing that the function holds when k+1 =n
Question 2
13+ 23+33----------+n3 = (1+2+……+n)2
=1+2+……+k+(k+1)2-(1+2+……..+k)2
=2(1+2+3+……..+n)= ( n(n+1)
22
= ( n+1 ) (n+2)
2
^2
Question 3
We first check the base where n=1 and evaluate with a point where both left and right hand sides
are equal i.e.

MATHEMATICS 19
∑
i=1
n
¿¿+2) = n ( n+1 ) (2 n+7)
6
∑
i=1
k +1
¿¿+2) = (k +1) ( K +1+1 ) (2(k +1)+7)
6
But ∑
i=1
n
¿¿+2) = n ( n+1 ) (n+1)
4
Thus ∑
i=1
n
¿¿+2) = n ( n+1 ) (2 n+7)
6 will be (k + 1) ( k +3 ) ( 2k +9)
6
Question 4
n2 > n+1
Let n=2
4>3
N=(k+1)2 leads to (k+1)>k+2 thus the prove holds when n>1
Question 5
2n3+3n2+n- divisible by 6
Using modular arithmetic
P(n)= 2n3+3n2+n
Then if n=0 (mod 2) then P(n) =0+0+0 = 0 mod 2
However, if n=1 mod 2 then, p(n)=2 +3+1=0 (mod 2)
P(n)= 2+3+2 = mod 3 f n= 2 mode 3

MATHEMATICS 20
Since both 2 and 3 divide p(n) then p(n) is multiple of 6
Question 6
7n – 2n –divisible by 5
7k+1-2k+1 =2+5. 7k-2.2k
7k-2k = 5z
7k= 5z+2k
Thus;
7k+1-2k+1 = 7.7k-2k+1= 35z+7.2k-2k+1
7k+1-2k+1 = 5.7k.5= (7k-2k):5
Question 7
11n-4n
Where n =1 then;
11-4 =7
11n-4n =7k
11(11n)-4(4n)
11(11n-4n) +7 (4n)
7(11k) + 7 (4n)
7(11k+4n)

MATHEMATICS 21
Question 8
an-bn =(a-b) = an-1+an-2+………+abn-2+bn-1
= a(an+an-1+ …..+abn-1)
=b(an-1b+……. abn-1+bn)
Subtracting i.e. a-b = an-bn
Question 9
32n+3+40n -27
By induction, we say that n=1 thus;
32+3+40 -27=64.k
32(n+1)+3+40(n+1)-27 = 9 (32n+3+40n-27)-320n+256
=9.64k-320n+256
=576k-320n+256
=64.(9k-5n+4)
Question 10
32n-1
For n=0, then 30-1 =0 which is a multiple of 8. Thus, using the induction steps,
32n-1= 9. 32n-1= (32n-1)+(8. 32n)
Question 11

MATHEMATICS 22
22n+1+1
=22(k+1)+1=22k+2+1
=4.22k+1
=4. (22k+1)+3
However, ∑
k=0
n −1
4k = 4n−1 ¿ ¿
3
Question 12
√ n ≤ ∑
k =1
n 1
k ≤ 2√n-1
Let n=0, thus;
√0 ≤ ∑
k =1
0 1
k ≤ 2√0-1 thus holding the prove when n=0 by induction method
Question 13
H2n ≥ 1+ n
2
When n=0, then p(0) = H20=H1= 1+ 0
2
By induction method;
P(n+1) = H2n+1 ≥ 1+ n+1
2
H2n+1=1+1/2+1/3+………… n
2n + n
2n+ 1+ --------+ n
2n+1

MATHEMATICS 23
= H2n + n
2n+ 1+ --------+ n
2n+1
≥ (1+ n
2) + n
2n+ 1+ --------+ n
2n+1
≥(1+ n
2) + ½
=1+ n+1
2
Question 14
b0= b1= b2=1 and bn= bn-1+ bn-3
a) bn-1¿ ¿)n-2 for n+1>3
Then;
bn-1 + bn-2¿ ¿)n-2+ ¿)n-4
=2bn-1
b) bn≤(3/2)n-1
bn+1≤ (3/2)n-1 if n=0, then;
b≤ (3/2)-1
Question 15
Prove that n!< nn for n found in Z is greater or equal to 2
= (k+1)!<(k+1)k+1
= (k+1+2)! < (k+1+2)k+1+2
When n =2, then 2!<22 which proves the induction method

MATHEMATICS 24
Question 16
Let n=1, then 1+x≥ 1+x
=1+x>0 = (1+x)k≥ 1+kx
=(1+x)k+1 ≥ (1+kx). (1+x)= (1+kx2) +(k+1)x ≥ 1+(k+1)x since kx2≥ 0
(1+x)k+1≥ (1+kx)(1+x)
=1+kx+x+kx2
=1+(k+1)x+kx2
≥ 1+(k+1)x