DISCRETE STRUCTURES

ABRAHAMLINCOLN

ProofMethods2.pptx

Home >Mathematics homework help >DISCRETE STRUCTURES

Proofs

Mathematical Systems

A mathematical system consists of:

Axioms/Postulate– everything that is assumed to be true (Well established)

Definitions – used for creating new concepts in terms of existing ones

Conjecture — a statement that is unproved, but is believed to be true

Axioms/Postulates Examples

Given two distinct points, there is exactly one straight line that connects them.

Given a line A and a point P not on A, there is exactly one line B parallel to the line A, and runs through the point.

For all real numbers x and y, xy = yx

Definitions Examples

Some definitions:

Two triangles are congruent if their vertices can be paired so that the corresponding sides and corresponding angles are equal.

Two angles are supplementary if the sum of their measures is 180˚.

The absolute value |x| of a real number x is defined to be x if x is positive or 0 and –x otherwise.

Mathematical Systems

Theorem – a proposition that has been proved to be true

Corollary – a theorem that follows easily from another theorem

Lemma – a theorem that is usually not too interesting in its own right but is useful in proving another theorem

Logic is a tool for the analysis of proofs

In this unit we will introduce some general methods of proof

Direct proofs, Counterexamples, Proof by Contradiction, Induction proofs…

Theorems Examples:

Some theorems:

If two sides of a triangle are equal, then their opposite angles are equal.

If the diagonals of a quadrilateral bisect each other, then the quadrilateral is a parallelogram.

For all real numbers x, y, and z, if x ≤ y and y ≤ z, then x ≤ z.

The corollary flows from the first theorem…

Examples:

A corollary example:

If a triangle is equilateral, then it is equiangular.

An example lemma:

If n is a positive integer, then either n-1 is a positive integer or n-1=0.

This result is not interesting on its own but could be used to prove other results.

Proofs

An argument that establishes the truth of a theorem is called a proof

Logic is a tool for the analysis of proofs

In this unit we will introduce some general methods of proof

Direct proofs, Counterexamples, Proof by Contradiction, Induction proofs…

Direct Proofs

Theorems are often of the form:

∀x1,x2,…,xn, if p(x1,x2,…,xn) then q(x1,x2,…,xn)

When will the above statement be true?

When the conditional proposition: “

Direct Proofs

Theorems are often of the form:

∀x1,x2,…,xn, if p(x1,x2,…,xn) then q(x1,x2,…,xn)

When will the above statement be true?

When the conditional proposition: “if p(x1,x2,…,xn) then q(x1,x2,…,xn)” is true for all x1,x2,…,xn in the domain of discourse.

For proving that the above statement is true, we only need to default)

Direct Proofs

Theorems are often of the form:

∀x1,x2,…,xn, if p(x1,x2,…,xn) then q(x1,x2,…,xn)

When will the above statement be true?

When the conditional proposition: “if p(x1,x2,…,xn) then q(x1,x2,…,xn)” is true for all x1,x2,…,xn in the domain of discourse.

For proving that the above statement is true, we only need to consider the case where p(x1,x2,…,xn) is true. Why?

If it’s false, it is vacuously true (true by default)

Direct Proofs

Theorems are often of the form:

∀x1,x2,…,xn, if p(x1,x2,…,xn) then q(x1,x2,…,xn)

When will the above statement be true?

When the conditional proposition: “if p(x1,x2,…,xn) then q(x1,x2,…,xn)” is true for all x1,x2,…,xn in the domain of discourse.

For proving that the above statement is true, we only need to consider the case where p(x1,x2,…,xn) is true. Why?

If it’s false, it is vacuously true (true by default)

Direct Proofs

A direct proof assumes that p(x1,x2,…,xn) is true and then, using:

p(x1,x2,…,xn)

Axioms

Definitions

Previously derived theorems (could be lemmas)

Inference

shows directly that q(x1,x2,…,xn) is true.

Example: Even and Odd Numbers

Definition: An integer n is even if there exists an integer k (odd or even) such that n = 2k.

Definition: An integer n is odd if there exists an integer k (odd or even) such that n = 2k+1.

Then n = 12 is even because ∃k, namely k = 6, such that n = 2k; that is, 12 = 2∙6.

Then n = -21 is odd because ∃k, namely k = -11, such that n = 2k+1; that is, -21 = 2∙(-11)+1.

Example: Even and Odd Numbers

Definition: An integer n is even if there exists an integer k (odd or even) such that n = 2k.

Definition: An integer n is odd if there exists an integer k (odd or even) such that n = 2k+1.

Then n = 12 is even because ∃k, namely k = 6, such that n = 2k; that is, 12 = 2∙6.

Then n = -21 is odd because ∃k, namely k = -11, such that n = 2k+1; that is, -21 = 2∙(-11)+1.

Direct Proof (Example-1)

Claim: For all integers m and n, if m is odd and n is even, then m+n is odd.

In a direct proof, we assume the hypotheses and derive the conclusion

m is odd and n is even (Hypotheses)

… (this is the part of the proof that needs to be … completed)

∴ m+n is odd. (Conclusion)

Direct Proof

Claim: For all integers m and n, if m is odd and n is even, then m+n is odd.

Proof: m is odd and n is even (Hypotheses)

∃k1∈ Z such that m = 2k1+1 (because m is odd)

∃k2∈ Z such that n = 2k2 (because n is even)

Then, m+n = (2k1+1)+(2k2) = 2(k1+k2)+1

Let k= k1+k2, then, m+n =2k+1, which means

∃k∈ Z, such that m+n =2k+1 ∴ m+n is odd. (Conclusion)

Direct Proof (Example-2)

Claim: For all sets X, Y, and Z, X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Proof:

X, Y, and Z are sets (Hypotheses)

…

∴ X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Direct Proof

Claim: For all sets X, Y, and Z, X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Proof:

X, Y, and Z are sets (Hypotheses)

…

∴ X ∩ (Y–Z) = (X∩Y) – (X∩Z)

What are the definitions we know about sets and set equality?

Set Equality

Recall that X ∩ (Y–Z) = (X∩Y) – (X∩Z) if :

If a∈(X∩(Y–Z)), then a∈((X∩Y) – (X∩Z))

and

If a∈((X∩Y) – (X∩Z)), then a∈ (X∩(Y–Z))

Direct Proof

Claim: For all sets X, Y, and Z, X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Proof:

X, Y, and Z are sets (Hypotheses)

Lemma1:If a∈(X∩(Y–Z)), then a∈((X∩Y) – (X∩Z))

Lemma2:If a∈((X∩Y) – (X∩Z)), then a∈(X∩(Y–Z))

∴ X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Direct Proof

Lemma 1: If a∈(X∩(Y–Z)), then a∈((X∩Y) – (X∩Z))

Proof:

Let a∈(X∩(Y–Z))

By definition a∈X and a∈(Y–Z)

a∈Y and a∉ Z (since a∈(Y–Z))

To show that a∈((X∩Y) – (X∩Z)), we need to show that a∈(X∩Y), a ∉ (X∩Z )

a∈(X∩Y) (since a∈X and a∈Y)

a ∉ (X∩Z ) (since a∉ Z)

Then, a∈(X∩Y) and a∉ (X∩Z)

∴ a∈((X∩Y) – (X∩Z))

Direct Proof

Lemma 2: If a∈((X∩Y) – (X∩Z)) , then a∈(X∩(Y–Z))

Proof:

Let a∈((X∩Y) – (X∩Z))

By definition a∈(X∩Y) and a∉ (X∩Z)

a∈X and a∈Y (since a∈(X∩Y))

a∉ Z (since a∉ (X∩Z) and a∈X)

To show that a∈(X∩(Y–Z)), we need to show that a∈X, which we did above, and a∈(Y–Z)

a∈(Y–Z) (since a∈Y and a∉ Z, shown above )

Then, a∈X and a∈(Y–Z)

∴ a∈(X∩(Y–Z))

Direct Proof

Claim: For all sets X, Y, and Z, X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Proof: X, Y, and Z are sets (Hypotheses)

If a∈X∩(Y–Z), then a∈(X∩Y) – (X∩Z)

(by Lemma 1)

If a∈(X∩Y) – (X∩Z), then a∈X∩(Y–Z)

(by Lemma 2)

∴ X ∩ (Y–Z) = (X∩Y) – (X∩Z)

Direct Proof (Example-3)

Claim: If d = min{d1,d2} and x ≤ d, then x ≤ d1 and x ≤ d2.

Definition: If d = min{d1,d2}, then:

If d1 ≤ d2, then d = d1

If d2 < d1, then d = d2

Do on the board!!!!!!

Direct Proofs

Claim: If d = min{d1,d2} and x ≤ d, then x ≤ d1 and x ≤ d2.

Proof Outline:

Let d, d1, d2, and x∈ R

Let d = min{d1,d2} and x ≤ d

…

∴ x ≤ d1 and x ≤ d2

Direct Proofs

Claim: If d = min{d1,d2} and x ≤ d, then x ≤ d1 and x ≤ d2.

Proof:

Let d, d1, d2, and x∈ R

Let d = min{d1,d2} and x ≤ d

Then, if d1 ≤ d2, then d = d1 and otherwise (d2 < d1), d = d2

In any case, d ≤ d1 and d ≤ d2.

d ≤ d1: Since x ≤ d and d ≤ d1, then x ≤ d1.

d ≤ d2: Since x ≤ d and d ≤ d2, then x ≤ d2.

∴ x ≤ d1 and x ≤ d2

Direct Proofs (Example-4)

Claim: X∪(Y–X) = X∪Y, for all sets X, Y, Z

Proof:

Let a∈X∪(Y–X), we need to show that a∈(X∪Y)

By definition, a∈X or a∈(Y–X)

If a∈X then a∈(X∪Y)

If a∈(Y–X) then a∈Y, and therefore a∈(X∪Y) also

∴ a∈(X∪Y)

Direct Proofs (Example-4)

Now, let a∈(X∪Y), we need to show that a∈X∪(Y–X)

Since a∈(X∪Y) by assumption, then by definition, a∈X or a∈Y

If a∈X, then a∈X∪(Y–X)

If a ∉ X, and a∈Y and then a∈(Y–X)

∴a∈X∪(Y–X)

∴ X∪(Y–X) = X∪Y

Direct Proof: (Example-5)

Example Theorem: 1 + 2 + 3 + … + n = n(n+1)/2

Proof: Let x = 1 + 2 + 3 + … + (n-2)+(n-1)+n. Then

x = n + (n-1) + (n-2) + … + 3 + 2 +1. [commutative]

Notice, the two equations above are the same, one is listed in increasing order (I to n) and the second is listed in decreasing order (n to 1)

add the previous two equations, by adding corresponding parameters (1 to n, 2 to (n-1), and so on):

So, 2x = (n+1) + (n+1) + (n+1) + … + (n+1)+(n+1) = n(n+1)

So, x = n(n+1)/2.

Proof by Contradiction

In a proof by contradiction, we assume that what we want to prove is not true, and then show that the consequences of this are not possible.

That is, the consequences contradict either what we have just assumed, or something we already know to be true (or, indeed, both) - we call this a contradiction.

Proof by Contradiction

for a statement p→q:

We assume the hypothesis (p is true)and assume that q is actually false

Then, using that and other definitions and theorems, we reach a conclusion that our hypothesis p is False

Since a contradiction is reached, then q must be True

Proof by Contradiction, Example

Claim: For every n∈Z, if n2 is even, then n is even.

Proof (by contradiction):

Let n∈Z, such that n2 is even

Assume to the contrary that n is odd

Proof by Contradiction

Claim: For every n∈Z, if n2 is even, then n is even.

Proof (by contradiction): Let n∈Z, such that n2 is even

Assume to the contrary that n is odd

Then ∃ j∈Z such that n=2j+1

Then n2 = (2j+1)2 = 4j2+4j+1 = 2(2j2+2j) + 1, but this is in the form of 2k+1, (where k= 2j2+2j), and a number in this form is odd,

Then n2 is odd. CONTRADICTION. ∴ n is even

Proof by contradiction example 2

Theorem (by Euclid): There are infinitely many prime numbers

Proof. Assume there are a finite number of primes

List them as follows: p1, p2 …, pn, starting from 2, 3, 5, …., pn

Consider the number q = p1p2 … pn + 1

q is either a prime, which means there is a larger prime (contradiction to our assumption), or it is not prime. If it is not prime, then:

q must be divisible by a prime other than the listed primes, and this prime must be larger than pn, which means there is a larger prime and our assumption is wrong.

We conclude that q is either a prime, or divisible by a prime that must be larger than any of the primes listed above

This contradicts our assumption that all primes are in the list p1, p2 …, pn

Proof by contradiction example 3

Prove that if n3+5 is odd, then n is even

Assume p (n3+5) is true, which means odd and q (n) is false, which means n is odd, if n is odd then:

n=2k+1 for some integer k (definition of odd numbers)

n3+5 = (2k+1)3+5 = 8k3+12k2+6k+6 = 2(4k3+6k2+3k+3)

As 2(4k3+6k2+3k+3) is 2 times an integer, it must be even, contradiction to our assumption that it is odd.

Contradiction!

Proof by Mathematical Induction

Review of Sigma Notation

For a sequence of numbers aj with j ≥ 1, we use the notation

to denote the sum of the first n terms of the sequence. This is called sigma notation for the sum.

In other words

Examples of Sigma Notation

)

More on Sigma Notation

The above formula from our previous example can be generalized as follow:

Another example:

The initial value of the index variable can be any integer.

The final value of the index variable must be greater than or equal to the initial value of the index variable.

1 + 3 + 5 + 7 +9 + 11 = 36

1 + 3 + 9 + 27 + 81 = 121

(1/2) + (1/6) + (1/12) + (1/20) + (1/30) = 5/6

Examples of Sigma Notation

Evaluate each of the following sums:

1 + 3 + 5 + 7 +9 + 11 = 36

1 + 3 + 9 + 27 + 81 = 121

(1/2) + (1/6) + (1/12) + (1/20) + (1/30) = 5/6

Examples of Sigma Notation

Write the following sums in sigma notation.

The Principle of Mathematical Induction

Mathematical induction is a method of proof

To prove that P(n) is true for all natural numbers n, we complete two steps

Basis Step: Verify that P(1) is true.

Induction Step: Show that the conditional statement “if P(k), then P(k + 1)” is true for all positive integers k.

Example 1

Show that if n is a natural number, then

First, notice that the left hand side can be written using sigma notation.

So let P(n) be

for all natural numbers.

Prove for all natural numbers.

Before we use mathematical induction, lets see what this means using an example when n=6::

1. P(6)

LHS: 1 + 2 + 3 + 4 + 5 + 6 = 21

RHS: [(6)(7)]/2 = 42/2 = 21

Thus P(6) is true.

Prove for all natural numbers.

PROOF: We will prove this by mathematical induction.

Basis Step: We must show P(1) is true.

P(1) states

The left hand side is 1

The right hand side is [1(2)]/2 = 1

Since 1 = 1, P(1) is true.

Prove for all natural numbers.

Induction step: We must show the conditional statement “if P(k), then P(k + 1)” is true for all natural numbers k.

We will use a direct proof on this.

We will assume P(k) is true.

Then we will show that P(k + 1)is true.

Prove for all natural numbers.

So in the induction step:

P(k ) is equivalent to

We will assume this is true

Then we will show that P(k + 1) is true

Now P(k + 1) states

Showing the above is the goal of the induction step.

Now

This shows .

This shows . Thus we have shown if P(k), then P(k + 1) is true for all positive integers k.

This shows . Thus we have shown if P(k), then P(k + 1) is true for all positive integers k. The induction step is complete.

Therefore we have shown by mathematical induction that is true for all natural numbers.

Reviewing the Principle of Mathematical Induction

To prove that P(n) is true for all natural numbers n, we complete two steps.

Basis Step: Verify that P(1) is true.

Inductive Step: Show that the conditional statement “if P(k) then P(k + 1)” is true for all positive integers k.

Example 2

Conjecture a formula for the sum of the first n positive odd integers. Then prove your conjecture using mathematical induction.

n	Sum of the first n positive odd integers
1	1
2	1 + 3 = 4
3	1 + 3 + 5 = 9
4	1 + 3 + 5 + 7 = 16
5	1 + 3 + 5 + 7 + 9 = 25
6	1 + 3 + 5 + 7 + 9 + 11 = 36

= 12

= 22

= 32

= 42

= 52

= 62

Sum of the first n odd natural numbers is n2.

From these values it seems reasonable to conjecture that the sum of the first n positive odd integers is n2.

That is 1 + 3 + 5 + … + (2n – 1)

= (21 – 1) + (22 – 1) + (23 – 1) + … + (2n – 1) = n2.

The left hand side can be written as

Let P(n) denote the proposition that the sum of the first n odd positive integers is n2.

That is, P(n) is

Sum of the first n odd natural numbers is n2.

PROOF: (by Mathematical Induction)

Basis Step: P(1) is 1 = 12. Since this is true we have shown P(1) is true.

Sum of the first n odd natural numbers is n2.

PROOF: (by Mathematical Induction)

Basis Step: P(1) is 1 = 12. Since this is true we have shown P(1) is true.

Induction Step: Let be true.

Sum of the first n odd natural numbers is n2.

PROOF: (by Mathematical Induction)

Basis Step: P(1) is 1 = 12. Since this is true we have shown P(1) is true.

Induction Step: Let be true. . (We must show ).

It follows that

Thus we have shown if P(k), then P(k + 1).

Thus by mathematical induction the sum of the first n odd natural numbers is n2.

Reviewing the Principle of Mathematical Induction

To prove that P(n) is true for all natural numbers n, we complete two steps.

Basis Step: Verify that P(1) is true.

Inductive Step: Show that the conditional statement “if P(k) then P(k + 1)” is true for all positive integers k.

Example 3

Use mathematical induction to show that

1 + 2 + 22 + … + 2n = 2n + 1 – 1

for all whole numbers n.

Example for n=5, we have:

20+21+22+23+24+25 = 1+2+4+16+31= 63

25 + 1 – 1 =26-1 = 63

Preliminary work: Think about what you must show.

Note that the domain is whole numbers.

So, in the basis step we must show P(0) is true.

Example 3 (cont.)

Use mathematical induction to show that

1 + 2 + 22 + … + 2n = = 2n + 1 – 1

for all whole numbers n.

Preliminary work (cont):

In the inductive step, we must show “if P(k), then P(k + 1)” for all nonnegative integers k.

Now P(k) is =1 + 2 + 22 + … + 2k = 2k + 1 – 1

Show P(k + 1) is

= 1 + 2 + 22 + … + 2k + 2k + 1 = 2(k + 1) +1 – 1

= 2k + 2 – 1

Prove 1 + 2 + 22 + … + 2n = 2n + 1 – 1 for all whole numbers n

PROOF: (by Mathematical Induction) = 2n + 1 – 1

Basis Step: P(0) is true because 20 = 20+1 – 1 = 1. This completes the basis step.

Inductive Step: Assume that P(k) is true.

That is = 2k + 1 – 1 is true.

It follows that

= + 2k + 1

= (2k + 1 – 1 ) + 2k + 1

= (2k + 1 – 1) + 2k + 1

= 2k + 1 – 1 + 2k + 1

= 2 ∙ 2k + 1 – 1

= 2k + 2 – 1

We have completed the inductive step.

Because we have completed the basis step and the inductive step, by mathematical induction we know that P(n) is true for all nonnegative integers n. That is,

1 + 2 + 22 + … + 2n = 2n + 1 – 1 for all nonnegative integers n.

= a1 + a2 + a3 +!an

444444444440

=+++++++++=

(2)

12345

(2)(2)(2)(2)(2)

=-+-+-+-+-

(2)(4)(8)(16)(32)22

=-++-++-=-

(35)

(315)(325)(335)(345)

(355)(365)(375)(385)

=×-+×-+×-+×-

+×-+×-+×-+×-

(35)(65)(95)(125)(155)(185)(215)(245)

=-+-+-+-+-+-+-+-

(2)(1)(4)(7)(10)(13)(16)(19)

=-+++++++

(21)

(1)

135791136

=+++++=

1392781121

=++++=

11111

1223344556

=++++

×××××

111113010532505

2612203060606

++++

=++++===

(5)

(5)(5)(5)(5)(5)(5)(5)(5)(5)

-+-+-+-+-+-+-+-+-=

(4)

(34)(24)(14)(04)(14)

-++-++-+++++=

48121620242832

+++++++=

1+ 2 + 3+!+ n =

n(n +1) 2

(1)

6(61)

states

1(11)

(1)

jjk

æö

=++

ç÷

èø

åå

(1)

jjk

æö

=++

ç÷

èø

=++

åå

(1)

(1)2(1)

jjk

kkk

æö

=++

ç÷

èø

=++

åå

(1)

(1)2(1)

jjk

kkk

æö

=++

ç÷

èø

=++

+++

åå

(1)

(1)2(1)

jjk

kkk

æö

=++

ç÷

èø

=++

+++

åå

(1)

(1)2(1)

(1)(2)

jjk

kkk

æö

=++

ç÷

èø

=++

+++

åå

(1)(2)

(21)

(21)(1)

-=+

(21)(21)(2(1)1)

jjk

-=-++-

åå

(21)(21)(2(1)1)

(21)(221)

jjk

-=-++-

=-++-

åå

(21)(21)(2(1)1)

(21)(221)

(21)(21)

jjk

-=-++-

=-++-

=-++

åå

(21)(21)(2(1)1)

(21)(221)

(21)(21)

jjk

-=-++-

=-++-

=-++

=++

åå

(21)(21)(2(1)1)

(21)(221)

(21)(21)

(1)

jjk

-=-++-

=-++-

=-++

=++

åå