Dis Math Techniques1

7/31/2019 Dis Math Techniques1

1/39

Discrete Mathematics-1

ByProf. Manohar Lal

Director

School of Computer and Information SciencesIndira Gandhi National Open University

New Delhi-110068.

Jan 07, 2012


2/39

Text: Elements of Discrete Mathematics

by C. L. Liu (McGraw Hill, 1985)

References:(1)Discrete Maths and Its Applications

Kenneth H. Rosen (TMH 2003)

(2) Discrete Match Structures with Applicationsto Computer Science,By Trembley & Manohar

(TMH 1975, 1997)

(3) Discrete Mathematics by Richard byJohnsoubaugh (Fifth edition,Pearson, 2001)

(4) Discrete Mathematics with Graph Theory

E.G. Goodaire & M.M. Parmenilor (PH, 2002)


3/39


4/39

A computer can not represent real number

system in its entirety, it can essentially

represent only the integers------machine-

epsilon---the smallest positive integer

representable in the machine. Thus,

Computer math is essentially Discrete

mathematics


5/39

The number of natural numbers is essentially

the same as the number of integers, is thesame as the number of rational numbers

Consider the mappings

1 2 3 4 5 6.0 1 -1 2 -2 3..

0, 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3,

1/4, 5/1, 4/2, 3/3, 2/4, 1/5, However, the number of real numbers is

strictly more than the number of integers

through diagonalization method


6/39

The number systems (N, +), (N, .), ( I, +), (I, .)(I, +, .),(Q,+), (Q, .), (Q, +, .), (R,+), (R, .), (R, +, .)

(C,+), (C, .), (C, +, .)

(R, +, .) is ordered field

(C, +, .) is not an ordered field

(R, +, .) is complete ordered field


7/39

Set Theory.Set operations.union,

intersection, complementation, symmetric

difference

Finite sets, countably infinite sets, uncountably

infinite sets


8/39

Proof Techniques in Discrete

MathematicsProof by casesConstructive Existence

Non-constructiveMathematical InductionPigeon-Hole Principle

Diagonalization methodto show strictlylarger sets

Principle of inclusion and exclusionSymbolic logical techniques direct, bycontradiction b contra osition


9/39

Proof by cases

(p1 V p2 V p3pn) q

[( p1q) (p2q) .. (pnq)]

Problem: Show there are no solutions for integers x & y

Such that x2 + 3y2 = 8

Case (i) x2

> 8 ,i.e, x 3Case (ii) 3 y2> 8 i.e y 2

Case (iii) x = -2, -1, 0, 1, or 2 &

y = -1, 0, 1

possible values for x2 = 0, 1, 4

possible values for 3y2 = 0, 3

Maximum (x2 + 3y2) = 7


10/39

Constructive Existence Proof

X P(x) is shown by the existence of a such that P(a)

Problem: show that a positive integer can be written as sum of

two cubes in two different way

Solution: 1729 = 103 + 93 = 123 + 13

Non-constructive existence proof

Problem: For some irrationals x and y, xy is rational

Solution: xy

is rational: (2 )2

or ((2 )2

)2

= 2 is rational


11/39

MathematicalInduction


12/39

1. The Principle of Mathematical Induction

Consider the following series

1 = 12

1 + 3 = 22

1 + 3 + 5 = 32

1 + 3 + 5 + 7 = 4

2

Is 1 + 3 + 5 + 7 + . + (2n-1) = n2 ?


13/39

Is it true whenn

= 2800 ?When n = 2800

LHS = 1 + 3 + 5 + 7 +. + (2(100)-1)

= 1 + 3 + 5 + 7 + . + 199

= 10000

RHS = 1002

= 10000The proposition is true for n = 2800


14/39

Apply Mathematical Induction

(M.I.) to prove the propositionA proposition P(n) is true for all positive

integers n ifboth of the following conditions

are satisfied :

Is it true when n = 100000 ?

1. P(1) is true.

2. AssumingP(k) is true for any positive

integer k, it can be proved thatP(k+ 1) is

also true.



15/39



16/39

Note :

Mathematical induction cannot be used to

prove whose variables are not positiveintegers.

For instance : it is a serious mistakes to

prove the identity

x3 1 = (x - 1)(x2 +x + 1), for allxR.



17/39

Prove by mathematical induction that

1 + 3 + 5 + . + (2n 1) = n2 for all positive

integers.

LetP(n) be the proposition 1 + 3 + 5 + 7 + . + (2n 1) = n2

When n = 1, RHS = 12 = 1

LHS = 1

P(1) is true.

AssumeP(k) is true for any positive (+ve) integerk.

i.e. 1 + 3 + 5 + 7 + . + (2k1) = k2

When n = k+ 1, RHS = (k+ 1)2

2. Some Simple Worked Examples


18/39

k2

P(n) is true for n = k+ 1 if n = kistrue .

By M.I.,P(n) is true for all +ve integers n.

LHS = 1+3+5+7+ . +(2k 1) + [2(k+1) 1]

= k2 +2k+ 2 1

= k2 +2k+ 1

= (k+ 1)2


1 + 3 + 5 + 7 + . + (2k1)


19/39

Further Examples of

Mathematical Induction



20/39

Prove by mathematical induction that

8n 3n is divisible by 5 for all positiveintegers n.

Let P(n) be the proposition 8n 3n is divisible

by 5 .When n = 1, 81 31 = 5 which is divisible by

5.

P(1) is true.

Assume P(k) is true for any positive integerk.

i.e. 8k 3k = 5N, where N is an integer.



21/39

When n = k+ 1

8k+1 3k+1=88k 33k

=88k 33k 53k + 53k

=88k 83k + 53k=8(8k 3k) + 53k

=8(5N) + 53k

=5(8N + 3k) which is divisible by 5 P(n) is true for n = k+ 1 if n = kis

true .



22/39

3. Variations of the Method of

Induction

(A) 1st type of variation :

LetP(n) be a proposition involving

positive integern.

If (i) P(n) is true for n = 1 and n = 2

and (ii) ifP(n) is true for some positive

integers kand k + 1,then

P(n) is also true forn = k+ 2,

thenP(n) is true for all positive integers n.


23/39


Induction

(A) 1st type of variation :

Note :

The principle may be applied

to the proposition of the forman - bn oran + bn.


24/39


Induction

(B) 2nd type of variation :

LetP(n) be a proposition involving integern.

If (i)P(n) is true n = ko, where ko is an integer

not necessarily equals 1, and

(ii) ifP(n) is true forn = k(k k0) thenP(n)is

also true forn = k+ 1.

thenP(n) is true for all integers n ko.

3 V i ti f th M th d f


25/39


Induction

(B) 2nd type of variation :

.2,5

integerpositiveeveryforthatProve..

2nn

ge

n>

.52..255

,322,5)(

2

2

5

=>

==

===

nfortrueisneiRHS

LHSnWheni

n

3 V i ti f th M th d f


26/39


Induction

(C) 3rd type of variation :LetP(n) be a proposition involving integer

n.

If (i)P(n) is true forn = 1 and n = 2,

and (ii) ifP(n) is true for some positive

integerk, thenP(n) is also true forn = k+ 2,

thenP(n) is true for all positive integers n.


27/39


Induction

(C) 3rd type of variation :Remarks :

In the above statement, if we only checkP(n) is true forn = 1 (respectively n = 2),

we can only conclude thatP(n) is true for

all positive odd (respectively, even)

integers n.


28/39


Induction

(C) 3rd type of variation :

])1(1[4

1

)1(2

1

)(is

2

equationtheofsolutions

integralnegativenonof)(numberthe

,integerpositiveeachforthatProve..

n

nnf

nyx

nf

nge

+++=

=+


29/39

Pigeonhole principle

The pigeonhole principle [Rosen, p.347]: Ifk is placed into kboxes,

then there is at least one a positive integer and k+1 or more objects are

box containing two or more objects.

.

A common way to illustrate this principle is by assuming that k+1 pigeons

fly to kpigeonholes. Then, there must be at least one pigeonhole containing at least

two pigeons.


30/39

The pigeonhole principle is a trivial observation,

which however can be used to prove many

results


31/39


Example 10.1: Let a, b, c be integers. We canchoose two of them whose sum is even.

Proof:

Apply the pigeonhole principle with odd and evenintegers as the two pigeonholes, and the a, b, c as

the three pigeons.

Two of the a, b, c have the same parity, that is, theyare both even, or both odd.

The sum of two even numbers, or the sum of two

odd numbers is even.


32/39


2/1

1/2

1/2

Example 10.2: Five points are given on, or inside a unit square.

Show that there is a pair of points whose distance is at most .

Proof: Split the unit square into 4 squares with edge 1/2, see the

figure. By the pigeonhole principle, two of the points are on, or inside

one of the four smaller squares.


33/39


Their distance is less or equal to the maximum distance between two

points of that square, that is, less or equal the diameter of the square.

By the Pythagorean theorem, the diameter of the small square is

2/14/14/1)2/1()2/1( 22 =+=+

1/2

1/2


34/39

Recursion

Recursively defined functions[Rosen, p.295]:We use two steps to define a function with the

set of nonnegative as its domain:

Basis step: Specify the value of the function atzero.

Recursive step: Give a rule for finding its value at

an integer from its values at smaller integers.

Such a definition is called recursive orinductive

definition.


35/39

Recursion

Exercise 10.3[Rosen, p.295]: Suppose thatfisdefined recursively by

f(0) = 3f(n + 1) = 2f(n) + 3

Findf(1),f(2),f(3), andf(4).

Exercise 10.4[Rosen, p.296]: Give a recursive

definition of the factorial functionf(n)=n!


36/39

Fibonacci numbers

In some recursive definitions of functions, the values of the

function at

the first kpositive integers are specified, and a rule is given

for

determining the value of the function at larger integers from

its values

at some or all of the preceding integers.


37/39

Fibonacci numbers: The Fibonacci numbers,f0,

f1,f2, , are defined recursively by

f0 = 0, f1 = 1

fn =fn - 1 +fn - 2

forn = 2, 3, 4, .


38/39

Fibonacci numbers

Example Letfn denote the n-th Fibonacci number.

Show that

when n is a positive integer.

Proof: For n=1

122

22

1 +=+++ nnn fffff

122

22

1 +=+++ nnn fffff


39/39

Fibonacci numbers

Exercise 10.6[Rosen, p.308, Ex.13]: Letfn denote

the n-th Fibonacci number. Show that

nn ffff 21231 =+++ when n is a positive integer.

Documents

Dis Math Techniques1