MTH202

PRACTICE QUESTION
WITH
SOLUTION
FOR FINAL TERM
LECTURE (23 TO 45)
 Solution File Lecture No 23-25

Question No.1:

Use mathematical induction to prove that 4n 3n 4 is true for integral values of n 2

Solution:

Let P(n) = 4n 3n 4

Let P n 4n 3n 4
BASIS STEP:
n 2
42 32 4 16 13
So P 2 is true
INDUCTIVE STEP:
Suppose P k is true for all k 2
4k 3k 4 1
we are to prove P k 1 is true i.e.
4k 1
3k 1
4 2
Now
1
LHS 4k 4k .4 4.(3k 4) 4.3k by (1) for k 2.
1
164 k 3k.(3 1) 16
1
4k 3k.3 3k 16
1 1
4k 3k 3k 4 12
1 1
4k 3k 4 12 3k
4k 1
3k 1
4 ignoring 12 as if a b c then a b
3k

Hence it is proved by mathematical induction that 4n 3n 4 is true for integral

values of n 2 .
Question No.2
3n(n
Use mathematical induction to prove that 3 6 9 ... 3n for all positive
1)
2
integers n.

Solution:
3n(n 1)
Let P n : 3 6 9 ... 3n
2
BASIS STEP:
LHS 3 1 3
3(1 1)
RHS =3
2
So P 1 is
true INDUCTIVE STEP:
Suppose P k is true for all k 1
3k (k 1)
3 6 9 ... 3k 1
2
we are to prove P k 1 is true i.e.
3 k 1 ( k 1 1)
P k 1 : 3 6 9 ... 3 k 1 2
2
Now
LHS 3 6 9 ... 3k 3 k 1 3 6 9 ... 3k 3 k 1
3k (k 1)
3 k
1 2k
3 k 1 1
2

k 2
3 k 1
2
3 k 1 k 1 1
RHS
2
Question No.3

Suppose n3 n is divisible by 6 is true for any positive integer. Justify the

statement for n = k+1.

Solution:
Inductive Step:
Suppose for n=k, k 3 k is dividible by
6 then k 3 k 6.q
3
we need to prove k 1 k 1 is dividible by 6
3
k 1 k 1 k 3 3k 2 3k 1 k 1
k3 k 3k k 1
6.q 3k k 1
As the k k 1 of integers is even so we can take as 2r
product
6.q 3k k 1
6.q 3.2r
6 q r
3
So k 1 k 1 is dividible by 6
Hence by induction method, n3 n is divisible 6

Question No 4:

Suppose 5n 1 is divisible by 4 is true for n k . Justify the statement for n k 1.

Solution:
Inductive Step:
Let for n k , 5k 1 is divisible by 4
then 5k 1 4.q
1
we need to prove that 5k 1 is divisible by 4
1
5k 1 5.5k 1
5k 4 1 1
5k.4 5k 1
5k.4 4.q
4 5k q
1
Hence 5k 1 is divisible by 4

Question No 5
Prove that if x divides y and y divides z then x divides z.

Solution:
By our assumptions, and the definition of divisibility, there are natural numbers k 1 and k2
such that
y xk1 and z yk2 .
Consequently,
z yk2 xk1k2 .
Let k Now k is a natural number and z xk , so by the definition of divisibility, x
k1k2
divides z.

Question No 6:
Show that for all integers a and b, if a b is even then a b is also even.

Solution:
Take a+b =
2k a= 2k-b
Subtracting ‘b’ from both
sides a-b =2k-b-b
a-b = 2k -
2b a-b = 2(
k-b)
Hence a-b is also even.
Question No 7:
Assume that m and n are particular integers. Justify your answer to each of the following:
1) Is 4m 6n even?
2) Is 8mn 5 odd?

Solution:
1) Yes: 4m+6n =2.(2m+3n) [by definition of even]
(2m+3n) is an integer because 2, 3, m, n are integers and products and
sums of integers are integers.
2) Yes: 8mn+5 =2.(4mn+2)+1 [by definition of odd]
(4mn+2) is an integer because 4, 2, m, n are integers and products and
sums of integers are integers.
 Solution to Practice questions Lecture 26-28
Solution
1:

We are to prove by contradiction that 4 3 2 is an irrational number. So, let’s assume that
4 3 2 is a rational number. Then by definition of rational number, it can be written in the
following
form
a
4 3 for some integers a and b b 0
2 with
b
a
4 3 2
b
a
3 2 4
b
a 4b
2
3b

Since a and b are integers, so are a-4b and 3b with 3b 0 . This shows 2 is a rational number.
that
Which is a contradiction to the f act that2 is an irrational number. This contradiction shows that
our initial supposition was incorrect and thus, 4 2 is not an irrational number that is 4 23
3
is a rational number.

Solution 2:
We are to prove by contradiction that if 5n 1 is odd then n is even. Suppose for some integer n
, 5n 1 is odd but n is not even. That is n is odd. So it can be written as
n 2m 1 for some integer m.
5n 1 5(2m 1) 1
10m 6
2(5m 3)

This shows that 5n 1 is equal to some multiple of 2 and so it is even which is a contradiction
to our initial supposition. So, the correct supposition will be that if 5n 1 is odd then n is
even.
Solution 3:

We are to prove by contraposition that if n2 is odd then n is odd. That is we are to prove that if n
is even then n2 is even.
Lets assume n is even. Then it can be written as a multiple of 2. That is
 n 2k for some integer k
n2 (2k )2
4k 2
2(2k 2 )

Clearly, is a multiple of 2 so n2 is also even.

n2

This Proves that if is odd then n is odd.

n2

Solution 4:
The following are pre and post conditions.

Pre-condition: The input variables a and b are positive integers.

Post-condition: The output variable q and r are positive integers such that

a = b · q + r and 0 ≤r < b.
Solution 5:
We are to find the GCD (61114,
94). Divide 61114 by 94
61114 94 650 14
Divide 94 by 14
94 14 6 10
Divide 14 by 10
14 10 1 4
Divide 10 by 4
10 4 2 2
Divide 4 by 2
4 2 2 0
Thus, the GCD of 61114 and 94 is 2.
 Solution to practice questions for Lecture No. 29-31

Solution 1:
For a round trip, the person will travel from city A to B, B to C then C to B and then B to A i.e.,
A B C B A
The person can travel 3 ways from A to B and 5 ways from B to C and back that is
3 5 5 3
A B C B A

Thus, there are

3 5 5 3 225
ways to have a round
trip.
Solution 2:
Each bit (binary digit) is either 0 or 1.
Hence, there are 2 ways to choose each bit. Since we have to choose seven bits therefore, the
product rule shows, there are a 2 2 2 2 2 2 2 27 128
total of
Solution 3:
Given that
p(n,2)=42

That is
n!
42
(n 2)!
n(n 1)(n 2)!
42
(n 2)!
n(n 1) 42
n2 n 42 0
n2 7n 6n 42 0
n(n 7) 6(n 7) 0
(n 6)(n 7) 0
n 6, n 7

Ignoring the negative value, the desired value of n is 7.

Solution 4:
5 boys can be selected from 10 in following number of ways
10
C5 252
5 girls can be selected from 15 in following number of ways
15
C5 3003
Total number of ways a team of 10 students be selected = 252 3003=756756

Solution 5:
There are 13 Spade cards in a deck of cards so C(13,2) =
78 There are 13 Heart cards in a deck of cards so
C(13,2) = 78
C 13, 2 C 13, 2 78 78 6084
 Practice questions Lectures 32-34

Question No 1:

How many distinguishable ways can the letter of the word HULLABALOO be arranged?

Question No 2:

How many signals can be given by 7 flags of different colors using 3 flags at a time?

Question No 3:

How many 4-digit numbers can be formed by using each of the digits1, 2, 3,4,5,6 only once?

Question No 4:
Suppose that there are 2000 students at your university. Of these 500 are taking a course in
computer science, 670 are taking a course in mathematics and 300 are taking course in
both computer science and mathematics. How many are taking a course either in computer
science or in mathematics?

Question No 5:
There are 24 students in a class, only 13 are willing to go to a tour for Murree. In how
many ways can these be chosen?

Question No 6:

In an office, there are 75 faculty members can speak Malay(M ) and 25 can speak Chinese
(C), while only 10 can speak both Malay and Chinese. Using Inclusion-exclusion Principle
find how many faculty members can speak either Malay (M) or Chinese(C)?
 Practice Questions for Lecture No. 35 to 37

Question 1:
A box contains seven discs numbered 1 to 7. Find for each integer k ( k is from 3 to
11) , the probability that the numbers on two discs drawn without replacement have a sum
equal to k.
Question 2:
A die is weighted so that the outcomes produce the following probability distribution:
Outcome 1 2 3 4 5 6
Probability 0.1 0.3 0.2 0.1 0.1 0.2

Consider the event A = {odd number occur on die} then P(A) and P(Ac ) .
find

Question 3:
There are 20 girls and 40 boys in a class. Half of the boys and half of the girls
have blue eyes. Find the probability that one student chosen as monitor is either a girl or a
student having blue eyes.
Question 4:
A pair of fair dice is thrown. Find the probability P that the sum is 9 or greater if
(i) 5 appear on first die
(ii) 5 appear on at least one die
 Prcatice Question Lecture No 39-41
Question No 1:

Find the maximum number of edges for a complete graph knby using handshaking theorem.

Solution

The total degrees in graphKn = 2 (number of edges in Kn)

n(n-1) = 2(number of edges in Kn)

Number of edges in n(n 1)

Kn 2

Question No 2:

Is the graph below is Complete Bipartite or not? Redraw the bipartite graph so that its
bipartite nature is evident?

Solution:
Yes it is a complete bipartite graph.

Question No 3:

Check whether the given graphs have an Euler circuit? If it does, find such a circuit, if it
does not, give an argument to show why no such circuit exists.

Solution:

In G1: each vertex has even degree so it an Euler circuit. In G2: vertices “c” and “b” has odd

degree so it is not an Euler circuit

Question No 4:

Find two Hamiltonian circuits of the following graph

 Solution:
(i) abcdefga ii) abcefgda

Question No 5:

Find the product AB and BA of the matrices (if not possible then give reason).
2 0 an
d 1 2 3
A 1 1 B 3 2 4

Solution:

2 0 1 2 3 2 0 4 0 6 0 2 4 6
AB 1 1 3 2 4 1 3 2 2 3 4 2 4 1

BA is not possible as B has 3 columns and A has two rows, so multiplication is not possible.

Question No 6:

Find the adjacency matrix of the graph shown below.

Solution:
 a b c d
a 0 0 1 0
b 0 0 1 2
c 1 1 0 1
d 0 2 1 0

Question No 7:

Draw a graph with the adjacency matrix.

11 1 0
1 011
11 0 1
0 110

with respect to the ordering of vertices a, b, c, d.

Solution:
 Lecture 41-43

Question No 1:

Find the product AB and BA of the matrices (if not possible then give reason).
2 0 an
d 1 2 3
A 1 1 B 3 2 4

Question No 2:

Find the adjacency matrix of the graph shown below.

Question No 3:

Draw a graph with the adjacency matrix.

11 1 0
1 011
11 0 1
0 11 0
with respect to the ordering of vertices a, b, c, d.

Question No 4 :

Find the degree sequence of the following graph.

Question No 5:

Draw all possible simple graphs with 2 vertices, which are non-isomorphic to each other.

Question No 6:
Determine whether the given graphs are isomorphic? (justify your answer)

Question No 7:
Suppose that a connected planar simple graph has 22 edges. If you want to draw a
graph having 11 faces, how many vertices does this graph have?

Question No 8:
Re-draw the given graph to prove it planar.
Question No 9:

Determine the chromatic number of the given graph.

 Practice Questions for Lecture No. 44 and 45

Question 1:
Find the total number of internal and terminal vertices of a full binary tree with nine vertices

Question 2:
Draw a binary tree with height 3 and having seven terminal vertices.

Question 3:
Draw any two non-isomorphic trees of five vertices.

Question 4:

Use Kruskal’s Algorithm to draw the minimal spanning tree for the graph given below.
Indicate the order in which edges are added to form a tree.

Question 5:
Find a spanning tree for the graph k1,5 ?