PARUL UNIVERSITY

FACULTY OF ENGINEERING AND

TECHNOLOGY
B. TECH. PROGRAMME (3rd SEM) (CSE/ IT)
DISCRETE MATHEMATICS (303191202)
ACADEMIC YEAR 2023-24

Unit-2: Principle of Mathematical Induction

Principle of mathematical induction

Let s(n) be any statement which is to be proved that it is true for all n∈ Z+ , we have to follow three steps for
it.
Step 1:- prove for n= no, the result is true where, no is initial value .this step is called basic/ initial step.
Step 2: Assume, for n=k, the result s(k) is true.
Step 3: prove for n= k+1 the result is true. This step is called inductive step. If all steps are valid, then s(n) is
true in general , for n∈Z+.

Ex : prove using mathematical induction,

1.2.3 + 2.3.4+ 3.4.5 +................. n(n+1)(n+2) = 1𝑛(𝑛+1)(𝑛+2)(𝑛+3)
4

Sol. Let S(n) :1.2.3 + 2.3.4+ 3.4.5 + ................. n(n+1)(n+2) = 1𝑛(𝑛+1)(𝑛+2)(𝑛+3)

4
For n=1,
S(1) : 1.2.3 +2.3.4 + ......... +1(1+1)(1+2) = 1(2)(3) = 6 = L.H.S.
1(1+1)(1+2)(1+3) 1(2)(3)(4)
R.H.S.= = =6
4 4

∴ L.H.S. = R.H.S.
S(n) is true for n=1.
Assume that S(n) is true for n=k
..............
S(k) : 1.2.3 + 2.3.4+ 3.4.5 +…………..k(k+1)(k+2) = 1𝑘(𝑘+1)(𝑘+2)(𝑘+3) (1)
4
We have to Prove that P(k+1) is also whenever P(k) is True
P(k+1): 1.2.3 + 2.3.4+ 3.4.5 +………k(k+1)(k+2)+(k+1)(k+2)(k+3) = 1(𝑘+1)(𝑘+2)(𝑘+3)(𝑘+4)
4

From equation 1 we have, 1𝑘(𝑘+1)(𝑘+2)(𝑘+3) + (k+1)(k+2)(k+3)

4

= (k+1)(k+2)(k+3)(1 𝑘+1) = 1 (𝑘 + 1)(𝑘 + 2)(𝑘 + 3)(𝑘 + 4)

4 4
= R.H.S.
L.H.S. = R.H.S
Therefore s(n) is true for all n=k+1 , Thus by principle of mathematical induction S(n) is true for all n∈ 𝑧+
Well Ordering Principle:
The well-ordering property states that every nonempty set of nonnegative integers has a least element.

THE WELL-ORDERING PROPERTY: Every nonempty set of nonnegative integers has a least element.

Example: Use the well-ordering property to prove the division algorithm. Recall that the division algorithm
states that if a is an integer and d is a positive integer, then there are unique integers q and r with 0  r  d and
a = dq + r .
Solution: Let S be the set of nonnegative integers of the form a − dq , where q is an integer. This set is
nonempty because −dq can be made as large as desired (taking q to be a negative integer with large absolute

value). By the well-ordering property, S has a least element r = a − dq0 .

The integer r is nonnegative. It is also the case that r < d. If it were not, then there would be a
smaller nonnegative element in S, namely, a − d (q0 +1) . To see this, suppose that r  d . Because a = dq0 + r ,

it follows that a − d (q0 +1) = (a − dq0 ) − d = r − d  0 . Consequently, there are integers q and r with 0  r  d .

Recursive Definitions:

Sometimes it is difficult to define an object explicitly. However, it may be easy to define this object in terms
of itself. This process is called recursion.

Recursively Defined Functions:

We use two steps to define a function with the set of nonnegative integers as its domain:

BASIS STEP: Specify the value of the function at zero.

RECURSIVE STEP: Give a rule for finding its value at an integer from its values at smaller integers. Such a
definition is called a recursive or inductive.

Example: Suppose that f is defined recursively by

f (0) = 3,
f (n +1) = 2 f (n) + 3
Find f (1), f (2), f (3)& f (4).

Solution: From the recursive definition it follows that

f (1) = 2 f (0) + 3 = 2 3 + 3 = 9
f (2) = 2 f (1) + 3 = 2 9 + 3 = 21
f (3) = 2 f (2) + 3 = 2 21+ 3 = 45
f (4) = 2 f (3) + 3 = 2 45 + 3 = 93

Example: Give a recursive definition of a n , where a is a nonzero real number and n is a non negative
integer.
Solution: The recursive definition contains two parts.
First a 0 is specified, namely, a0 = 1 . Then the rule for finding an+1 from a n , namely,
 an+1 = a n .a 1 , for n = 0, 1 , 2, 3 , . . . , is given. These two equations uniquely define a n
for all nonnegative integers n

The Division Algorithm

When an integer is divided by a positive integer, there is a quotient and a remainder, as the division algorithm
shows.

THE DIVISION ALGORITHM: Let a be an integer and d a positive integer. Then there are unique integers
q and r , with 0  r  d , such that a = dq + r .

Definition: In the equality given in the division algorithm, d is called the divisor, a is called the dividend,q
is called the quotient, and r is called the remainder. This notation is used to express the quotient and remainder:
q = a div d , r = a mod d

Example: What are the quotient and remainder when 101 is divided by 11?
Solution: We have 101 =11 9 + 2
Hence, the quotient when 101 is divided by 11 is 9 = 101 div 11, and the remainder is 2 =101 mod 11.

Example: What are the quotient and remainder when - 11 is divided by 3?

Solution: We have −11 = 3 (−4) +1
Hence, the quotient when - 11 is divided by 3 is -4 = -11 div 3, and the remainder is 1 = -11mod 3.
Note that the remainder cannot be negative. Consequently, the remainder is not -2, even though
−11 = 3 because r = -2 does not satisfy 0  r  3.

Primes:
A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p .
A positive integer that is greater than 1 and is not prime is called composite.
Remark: The integer n is composite if and only if there exists an integer a such that a / n and 1 a  n .

Example: The integer 7 is prime because its only positive factors are 1 and 7, whereas the integer 9 is
composite because it is divisible by 3.

THE FUNDAMENTAL THEOREM OF ARITHMETIC:

Every positive integer greater than 1 can be written uniquely as a prime or as the product of two or more
primes where the prime factors are written in order of non-decreasing size.

Example: The prime factorizations of 100, 641, 999, and 1024 are given by
100 = 2  2  5  5 = 22  52
641 = 641
999 = 3  3  3  37 = 33  37
1024 = 210

Remark: If n is a composite integer, then n has a prime divisor less than or equal to .

Example: Show that 101 is prime.

Solution: The only primes not exceeding 101 are 2, 3 , 5, and 7. Because 101 is not divisible by 2, 3, 5, or 7
(the quotient of 101 and each of these integers is not an integer), it follows that 101 is prime.
Greatest Common Divisors

Let a and b be integers, not both zero. The largest integer d such that d / a & d / b is called the greatest
common divisor of a and b . The greatest common divisor of a and b is denoted by gcd(a, b).

Example: What is the greatest common divisor of 24 and 36?

Solution: The positive common divisors of 24 and 36 are 1, 2, 3, 4, 6, and 12. Hence, gcd(24, 36) = 12 .

Example: What is the greatest common divisor of 1 7 and 22?

Solution: The integers 1 7 and 22 have no positive common divisors other than 1 , so that gcd( 17, 22) = 1 .

Euclidean Algorithm:
We will give a more efficient method of finding the greatest common divisor, called the Euclidean algorithm.
This algorithm has been known since ancient times.
Example: Find gcd (91,287) using Euclidean algorithm.
Solution: First, divide 287, the larger of the two integers, by 91, the smaller, 287 = 91 x 3 + 14 .Any divisor of
91 and 287 must also be a divisor of 287 - 91 x 3 = 14. Also, any divisor of 91 and 14 must also be a divisor
of 287 = 91 x 3 + 14.
Hence, the greatest common divisor of 91 and 287 is the same as the greatest common divisor of 91 and 14.
This means that the problem of finding gcd (9 1 , 287) has been reduced to the problem of finding gcd(91 , 14).
Next, divide 91 by 14 to obtain 91 = 14 x 6 + 7. Because any common divisor of 91 and 14 also divides 91 -
14 x 6 = 7 and any common divisor of 14 and 7 divides 91. Therefore gcd(91 ,14) = gcd( 14, 7). Continue by
dividing 14 by 7, to obtain 14 = 7 x 2. Because 7 divides 14, it follows that gcd( 14, 7) = 7. Furthermore,
because gcd(287, 91 ) = gcd(91 , 14) = gcd( 14, 7) = 7.

Remark: Let a = dq + r where a, b, q , and r are integers. Then gcd(a ,b) = gcd(b, r).
Example: Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.
Solution: Successive uses of the division algorithm give:
662 = 414 x 1 + 248
414 = 248 x 1 + 166
248 = 166 x 1 + 82
166 = 82 x 2 + 2
82 = 2 x 41.
Hence, gcd(414, 662) = 2, because 2 is the last nonzero remainder.

Basic Counting Principles:

Product Rule: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1
ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second

task, then there are n1n2 ways to do the procedure.

Sum Rule: If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1
ways is the same as any of the set of n2 ways, then there are n1 + n2 ways to do the task.
Example: A new company with just two employees, Sanchez and Patel, rents a floor of a building with
12 offices. How many ways are there to assign different offices to these two employees?
Solution: The procedure of assigning offices to these two employees consists of assigning an office to Sanchez,
which can be done in 12 ways, then assigning an office to Patel different from the office assigned to
Sanchez, which can be done in 11 ways. By the product rule, there are 12 x 11 = 132 ways to assign
offices to these two employees. ...
Example: The chairs of an auditorium are to be labeled with a letter and a positive integer not exceeding 100.
What is the largest number of chairs that can be labeled differently?
 Solution: The procedure of labeling a chair consists of two tasks, namely, assigning one of the 26 letters and
then assigning one of the 100 possible integers to the seat. The product rule shows that there are 26
x 100 = 2600 different ways that a chair can be labeled. Therefore, the largest number of chairs that
can be labeled differently is 2600. ...
Example: There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many
different ports to a microcomputer in the center are there?
Solution: The procedure of choosing a port consists of two tasks, first picking a microcomputer and then
picking a port on this microcomputer. Because there are 32 ways to choose the microcomputer and
24 ways to choose the port no matter which microcomputer has been selected, the product rule shows
that there are 32 x 24 = 768 ports.
Example: Suppose that either a member of the mathematics faculty or a student who is a mathematics major
is chosen as a representative to a university committee. How many different choices are there for this
representative if there are 37 members of the mathematics faculty and 83 mathematics majors and no
one is both a faculty member and a student?
Solution: There are 37 ways to choose a member of the mathematics faculty and there are 83 ways to choose
a student who is a mathematics major. Choosing a member of the mathematics faculty is never the
same as choosing a student who is a mathematics major because no one is both a faculty member
and a student. By the sum rule it follows that there are 37 + 83 = 120 possible ways to pick this
representative.
Example: A student can choose a computer project from one of three lists. The three lists contain 23, 15, and
19 possible projects, respectively. No project is on more than one list. How many possible
projects are there to choose from?
Solution: The student can choose a project by selecting a project from the first list, the second list, or the third
list. Because no project is on more than one list, by the sum rule there are 23 + 15 + 19 = 57 ways to
choose a project.

Inclusion-Exclusion Principle:

To correctly count the number of ways to do the two tasks, we add the number of ways to do it in one way
and the number of ways to do it in the other way, and then subtract the number of ways to do the task in a
way that is both among the set of n1 ways and the set of n2 ways. This technique is called the principle of

inclusion-exclusion. Sometimes, it is also called the subtraction principle for counting.

Example: How many bit strings of length eight either start with a 1 bit or end with the two bits 00?
Solution: We can construct a bit string of length eight that start with 1 in 27 =128 ways. This follows by the

product rule, because the first bit can be chosen in only one way and each of the other seven bits
can be chosen in two ways. Next we construct bit string of length eight that end with 00 in 26 =64
ways. This follows by the product rule, because the first 6 bits can be chosen in two ways and the
last two bits can be chosen in only one way. We construct a bit string of length eight that start with
1 and end with 00 in 25 =32 ways. which equals the number of ways to construct a bit string of

length eight that begin with a 1 or that ends with 00, equals 128 + 64 - 32 = 160 ways.

Example: A computer company receives 350 applications from computer graduates for a job planning a line
of new Web servers. Suppose that 220 of these people majored in computer science, 147 majored in
business, and 51 majored both in computer science and in business. How many of these applicants
majored neither in computer science nor in business?
Solution: To find the number of these applicants who majored neither in computer science nor in business, we
can subtract the number of students who majored either in computer science or in business (or
 both) from the total number of applicants. Let A1 be the set of students who majored in computer

science and A2 the set of students who majored in business. Then A1  A2 is the set of students

who majored in computer science or business (or both), and A1  A2 is the set of students who

majored both in computer science and in business. By the principle of inclusion-exclusion, the
number of students who majored either in computer science or in business (or both) equals
A1  A2 = A1 + A2 − A1  A2 = 220 + 147 - 51 = 316.

We conclude that 350 - 316 = 34 of the applicants majored neither in computer science nor in business.

The Pigeonhole Principle: If k is a positive integer and k + 1 or more objects are placed into k boxes, then
there is at least one box containing two or more of the objects. The pigeonhole principle i s also called the
Dirichlet drawer principle.

Generalized Pigeonhole Principle: If n pigeonholes are occupied by kn + 1 or more pigeons, where k is a

positive integer, then at least one pigeonhole is occupied by k + 1 or more pigeons

Remark: A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.
Example: Among any group of 367 people, there must be at least two with the same birthday, because there
are only 366 possible birthdays.
Example: In any group of 27 English words, there must be at least two that begin with the same letter,
because there are 26 letters in the English alphabet.

Permutations:
A permutation of a set of distinct objects is an ordered arrangement of these objects. We also are interested in
ordered arrangements of some of the elements of a set. An ordered arrangement of r elements of a set is called
an r-permutation.
n!
P(n, r) =
(n − r)!
Combinations:

A combination of these n objects taken r at a time is any selection of r of the objects where order does not
count. In other words, r-combination of a set of n objects is any subset of r elements.
n!
C(n, r) =
r!(n − r)!

Note: 1. 𝑃(𝑛 , 𝑛) = 𝑛!
2. 0! = 1
3. 𝐶(𝑛, 𝑛) = 1
4. 𝐶(𝑛, 𝑟) = 𝐶(𝑛, 𝑛 − 𝑟)
5. If n and r are positive integers , where 𝑛 ≥ r, then C(n,r-1)+C(n,r) = C(n+1,r)
Product rule: If an activity can be performed in r-successive steps and step 1 can be done in n1 ways, step 2
can be done in n2ways,…. Step r can be done in nr ways then the activity can be done in (n1,n2,n3,….nr) ways.
Sum rule: If r activities can be performed in n1,n2,n3,….nr ways and if they are disjoint , i.e cannot be
performed simultaneously , then any one of the r-activities can be performed in (n1+n2 +n3+….+nr) ways.
Note : Circular Permutation: The number of different circular arrangements of n objects = (n-1) !
Example: How many bit strings of length n contain exactly r 1’s?

Solution: The positions of r 1’s in a bit string of length n form an r-combination of the set
{ 1 , 2 , 3 , . . . , n}. Hence, there are C (n, r) bit strings of length n that contain exactly r 1’s.
Example: Suppose that there are 9 faculty members in the mathematics department and 11 in the computer
science department. How many ways are there to select a committee to develop a discrete mathematics
course at a school if the committee is to consist of three faculty members from the mathematics
department and four from the computer science department?
Solution: By the product rule, the answer is the product of the number of 3-combinations of a set with nine
elements and the number of 4-combinations of a set with 11 elements. By Theorem the number of
ways to select the committee is
9! • 11!
C(9,3) • C(11,4) = 4!7! = 84 • 330 = 27720
3!6!

Example: Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified
city, but she can visit the other seven cities in any order she wishes. How many possible orders can
the saleswoman use when visiting these cities?
Solution: The number of possible paths between the cities is the number of permutations of seven elements,
because the first city is determined, but the remaining seven can be ordered arbitrarily. Consequently,
there are 7 ! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 ways for the saleswoman to choose her tour. If, for
instance, the saleswoman wishes to find the path between the cities with minimum distance, and she
computes the total distance for each possible path, she must consider a total of 5040 paths !
Example: How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize
winner from 100 different people who have entered a contest?
Solution: Because it matters which person wins which prize, the number of ways to pick the three prize winners
is the number of ordered selections of three elements from a set of 100 elements, that is, the number
of 3-permutations of a set of 100 elements. Consequently, the answer is P ( l00, 3) = 100 ·99 · 98 =
970,200.
Example: A group of 30 people have been trained as astronauts to go on the first mission to Mars. How many
ways are there to select a crew of six people to go on this mission (assuming that all crew members
have the same job)?
Solution: The number of ways to select a crew of six from the pool of 30 people is the number of 6-
combinations of a set with 30 elements, because the order in which these people are chosen does not
matter. By Theorem 2, the number of such combinations is C(30, 6) = 30! 6! 24! = 30 · 29 · 28 · 27 ·
26 · 25 6 · 5 · 4 · 3 · 2 · 1 = 593,775.
Example: Suppose that there are 9 faculty members in the mathematics department and 11 in the computer
science department. How many ways are there to select a committee to develop a discrete mathematics
course at a school if the committee is to consist of three faculty members from the mathematics
department and four from the computer science department?
Solution: By the product rule, the answer is the product of the number of 3-combinations of a set with nine
elements and the number of 4-combinations of a set with 11 elements. By Theorem 2, the number of
ways to select the committee is C(9, 3) · C(11, 4) = 9! 3!6! · 11! 4!7! = 84 · 330 = 27,720.