Introduction to Proofs

Section 1.7
Section Summary 2

Mathematical Proofs
Forms of Theorems
Direct Proofs
Indirect Proofs
• Proof of the Contrapositive
• Proof by Contradiction
Proofs of Mathematical Statements
A proof is a valid argument that establishes the truth of a statement.
In math, CS, and other disciplines, informal proofs which are generally shorter, are
generally used.
• More than one rule of inference are often used in a step.
• Steps may be skipped.
• The rules of inference used are not explicitly stated.
• Easier for to understand and to explain to people.
• But it is also easier to introduce errors.
Proofs have many practical applications:
• verification that computer programs are correct
• establishing that operating systems are secure
• enabling programs to make inferences in artificial intelligence
• showing that system specifications are consistent
Definitions
A theorem is a statement that can be shown to be true using:
• definitions
• other theorems
• axioms (statements which are given as true)
• rules of inference
A lemma is a ‘helping theorem’ or a result which is needed to prove a theorem.
A corollary is a result which follows directly from a theorem.
Less important theorems are sometimes called propositions.
A conjecture is a statement that is being proposed to be true. Once a proof of a
conjecture is found, it becomes a theorem. It may turn out to be false.
Forms of Theorems
Many theorems assert that a property holds for all elements in a domain, such as
the integers, the real numbers, or some of the discrete structures that we will study
in this class.
Often the universal quantifier (needed for a precise statement of a theorem) is
omitted by standard mathematical convention.
For example, the statement:
“If x > y, where x and y are positive real numbers, then x2 > y2 ”

really means
“For all positive real numbers x and y, if x > y, then x2 > y2 .”
Proving Conditional Statements: p → q
Trivial Proof
Vacuous Proof
Direct Proof
Proof by Contraposition
Proof by Contradiction
Trivial Proof:

If we know q is true, then

p → q is true as well.
Vacuous Proof:

If we know p is false then

p → q is true as well.
[ Even though these examples seem silly, both trivial and vacuous proofs are often
used in mathematical induction) ]
Direct Proof:
Assume that p is true. Use rules of inference, axioms, and logical equivalences to
show that q must also be true.
Example: Give a direct proof of the theorem “If n is an odd integer, then n2 is odd.”
Solution: Assume that n is odd. Then n = 2k + 1 for an integer k. Squaring both sides
of the equation, we get:
n2 = (2k + 1)2 = 4k2 + 4k +1 = 2(2k2 + 2k) + 1= 2r + 1,
where r = 2k2 + 2k , an integer.
We have proved that if n is an odd integer, then n2 is an odd integer.

(marks the end of the proof. Sometimes QED is used instead.)

Definition: The real number r is rational if there exist integers p and q where q≠0
such that r = p/q
Example: Prove that the sum of two rational numbers is rational.
Proof by Contraposition: Assume ¬q and show ¬p is true also. This is sometimes
called an indirect proof method. If we give a direct proof of ¬q → ¬p then we have
a proof of p → q.
Example: Prove that if n is an integer and 3n + 2 is odd, then n is odd.
Example: Prove that for an integer n, if n2 is odd, then n is odd.
Proof by Contradiction:
Example: Prove that if you pick 22 days from the calendar, at least 4 must fall on the
same day of the week.
Example: Use a proof by contradiction to give a proof that √2 is irrational.
Proof by Contradiction 2

Prove that the sum of a rational number and an irrational number is irrational.
Theorems that are Biconditional Statements
To prove a theorem that is a biconditional statement, that is, a statement of the
form p q, we show that p → q and q →p are both true.
Example: Prove the theorem: “If n is an integer, then n is odd if and only if n2 is odd.”
Solution: We have already shown (previous slides) that both p →q and q →p.
Therefore we can conclude p q.
Sometimes iff is used as an abbreviation for “if and only if,” as in
“If n is an integer, then n is odd iff n2 is odd.”
What is wrong with this?
“Proof” that 1 = 2

Step Reason
1. a = b Prem ise
2. a 2 = a  b Multiply both sides of (1) by a
3. a 2 − b 2 = a  b − b 2 Subtract b 2 fr om both sides of ( 2 )
4. ( a − b ) ( a + b ) =b ( a − b ) Algebra on ( 3 )
5. a + b = b Divide both sides by a − b
6. 2 b = b Replace a by b in ( 5 ) because a = b
7. 2 = 1 Divide both sides of ( 6 ) by b

Solution: Step 5. a - b = 0 by the premise and division by 0 is undefined.

Proof Methods and Strategy
Section 1.8
Section Summary 3

Proof by Cases
Existence Proofs
• Constructive
• Nonconstructive
Disproof by Counterexample
Nonexistence Proofs
Uniqueness Proofs
Proof Strategies
Proving Universally Quantified Assertions
Open Problems
Proof by Cases 1

To prove a conditional statement of the form:

( p1  p 2   pn ) → q

Use the tautology

 ( p1  p 2   p n ) → q  

 ( p1 → q )  ( p 2 → q )   ( p n → q ) 

Each of the implications pi → q is a case.

Without Loss of Generality
Example: Show that if x and y are integers and both x∙y and x+y are even, then both
x and y are even.
Proof: Use a proof by contraposition. Suppose x and y are not both even. Then, one
or both are odd. Without loss of generality, assume that x is odd. Then x = 2m + 1
for some integer m.
Case 1: y is even. Then y = 2n for some integer n, so
x + y = (2m + 1) + 2n = 2(m + n) + 1 is odd.
Case 2: y is odd. Then y = 2n + 1 for some integer n, so
x ∙ y = (2m + 1) (2n + 1) = 2(2m ∙ n +m + n) + 1 is odd.
We only cover the case where x is odd because the case where y is odd is
similar. The use phrase without loss of generality (WLOG) indicates this.
Existence Proofs
Proof of theorems of the form  xP ( x ) .
Constructive existence proof:
• Find an explicit value of c, for which P(c) is true.
• Then  xP ( x ) is true by Existential Generalization (EG).

Example: Show that there is a positive integer that can be written

as the sum of cubes of positive integers in two different ways:
Proof: 1729 is such a number since
1729 = 103 + 93 = 123 + 13
Nonconstructive Existence Proofs
In a nonconstructive existence proof, we assume no c
exists which makes P(c) true and derive a contradiction.
Example: Show that there exist irrational numbers x and
y such that xy is rational.
Counterexamples
Recall  x  P ( x )   xP ( x ) .
To establish that  xP ( x ) is true (or  xP ( x ) is false)
find a c such that P(c) is true or P(c) is false.
In this case c is called a counterexample to
the assertion  xP ( x ) .

Example: “Every positive integer is the sum of the squares of

3 integers.”
The integer 7 is a counterexample. So the claim is false.
Uniqueness Proofs
Some theorems asset the existence of a unique element with a particular property,
!x P(x). The two parts of a uniqueness proof are
• Existence: We show that an element x with the property exists.
• Uniqueness: We show that if y≠x, then y does not have the property.
Example: Show that if a and b are real numbers and a ≠0, then there is a unique real
number r such that ar + b = 0.
Solution:
• Existence: The real number r = −b/a is a solution of ar + b = 0 because a(−b/a) + b = −b + b =0.
• Uniqueness: Suppose that s is a real number such that as + b = 0. Then ar + b = as + b, where r
= −b/a. Subtracting b from both sides and dividing by a shows that r = s.
Proof Strategies for proving p → q
Choose a method.
1. First try a direct method of proof.
2. If this does not work, try an indirect method (e.g., try to prove
the contrapositive).

For whichever method you are trying, choose a strategy.

1. First try forward reasoning. Start with the axioms and known
theorems and construct a sequence of steps that end in the
conclusion. Start with p and prove q, or start with ¬q and prove
¬p.
2. If this doesn’t work, try backward reasoning. When trying to prove
q, find a statement p that we can prove with the property p → q.
BACKWARD REASONING
Prove or disprove that if x2 is irrational, then x3 is irrational.
Mathematical Induction
Section 5.1
Section Summary 1

Mathematical Induction
Examples of Proof by Mathematical Induction
Mistaken Proofs by Mathematical Induction
Guidelines for Proofs by Mathematical Induction
Principle of Mathematical Induction
Principle of Mathematical Induction: To prove that P(n) is true for all positive
integers n, we complete these steps:
• Basis Step: Show that P(1) is true.
• Inductive Step: Show that P(k) → P(k + 1) is true for all positive integers k.
To complete the inductive step, assuming the inductive hypothesis that P(k) holds
for an arbitrary integer k, show that must P(k + 1) be true.
Proving a Summation Formula by Mathematical Induction
Example: Show that:
n
n ( n + 1)
= 2
Solution: i =1

• BASIS STEP: P(1) is true since 1(1 + 1)/2 = 1.

• INDUCTIVE STEP: Assume true for P(k).
The inductive hypothesis is k
k ( k + 1)
= 2
Under this assumption, i =1

k ( k + 1)
1+ 2 + + k + ( k + 1) = + ( k + 1)
2
k ( k + 1) + 2 ( k + 1)
=
2
( k + 1) ( k + 2 )
=
2
Proving Inequalities 1

Example: Use mathematical induction to prove that n < 2n

for all positive integers n.
Solution: Let P(n) be the proposition that n < 2n.
• BASIS STEP: P(1) is true since 1 < 21 = 2.
• INDUCTIVE STEP: Assume P(k) holds, i.e., k < 2k, for an
arbitrary positive integer k.
• Must show that P(k + 1) holds. Since by the inductive
hypothesis, k < 2k, it follows that:

k + 1  2 k + 1  2 k + 2 k = 2  2 k = 2 k +1
Therefore n < 2n holds for all positive integers n.
Proving Inequalities 2

Example: Use mathematical induction to prove that 2n < n!, for every integer n ≥ 4.
Solution: Let P(n) be the proposition that 2n < n!.
• BASIS STEP: P(4) is true since 24 = 16 < 4! = 24.
• INDUCTIVE STEP: Assume P(k) holds, i.e., 2k < k! for an arbitrary integer k ≥ 4. To show that P(k + 1)
holds:

2 k +1 = 2  2 k
 2k! (by the inductive hypothesis )
 ( k + 1) k !
= ( k + 1) !
Therefore, 2n < n! holds, for every integer n ≥ 4.

Note that here the basis step is P(4), since P(0), P(1), P(2), and P(3) are all false.
Proving Divisibility Results
Example: Use mathematical induction to prove that n3 − n is divisible by 3, for every
positive integer n.
Solution: Let P(n) be the proposition that n3 − n is divisible by 3.
• BASIS STEP: P(1) is true since 13 − 1 = 0, which is divisible by 3.
• INDUCTIVE STEP: Assume P(k) holds, i.e., k3 − k is divisible by 3, for an arbitrary positive integer k. To
show that P(k + 1) follows:
( k + 1)
3
( )
− ( k + 1) = k 3 + 3k 2 + 3k + 1 − ( k + 1)

= (k 3
) (
− k + 3 k2 + k )
By the inductive hypothesis, the first term (k3 − k) is divisible by 3 and the second term is
divisible by 3 since it is an integer multiplied by 3. So by part (i) of Theorem 1 in Section 4.1 ,
(k + 1)3 − (k + 1) is divisible by 3.
Therefore, n3 − n is divisible by 3, for every integer positive integer n.
Number of Subsets of a Finite Set 1

Example: Use mathematical induction to show that if S is a finite set with n elements,
where n is a nonnegative integer, then S has 2n subsets.
Tiling Checkerboards 1

Example: Show that every 2n × 2n checkerboard with one square removed can be tiled using right
triominoes. A right triomino is an L-shaped tile which covers three squares at a time.

Jump to long description

Important Points About Using Mathematical Induction
Mathematical induction can be expressed as the rule of inference

( P (1)   k ( P ( k ) → P ( k + 1) ) ) →  n P ( n ) ,
where the domain is the set of positive integers.
In a proof by mathematical induction, we don’t assume that P(k)
is true for all positive integers! We show that if we assume that
P(k) is true, then P(k + 1) must also be true.
Proofs by mathematical induction do not always start at the
integer 1. In such a case, the basis step begins at a starting point b
where b is an integer. We will see examples of this soon.
Validity of Mathematical Induction
Mathematical induction is valid because of the well ordering property, which
states that every nonempty subset of the set of positive integers has a least
element (see Section 5.2 and Appendix 1). Here is the proof:
• Suppose that P(1) holds and P(k) → P(k + 1) is true for all positive integers k.
• Assume there is at least one positive integer n for which P(n) is false. Then
the set S of positive integers for which P(n) is false is nonempty.
• By the well-ordering property, S has a least element, say m.
• We know that m can not be 1 since P(1) holds.
• Since m is positive and greater than 1, m − 1 must be a positive integer. Since
m − 1 < m, it is not in S, so P(m − 1) must be true.
• But then, since the conditional P(k) → P(k + 1) for every positive integer k
holds, P(m) must also be true. This contradicts P(m) being false.
• Hence, P(n) must be true for every positive integer n.
Guidelines:
Mathematical Induction Proofs
Template for Proofs by Mathematical Induction
1. Express the statement that is to be proved in the form “for all n ≥ b, P(n)” for a
fixed integer b.
2. Write out the words “Basis Step.” Then show that P(b) is true, taking care that the
correct value of b is used. This completes the first part of the proof.
3. Write out the words “Inductive Step”.
4. State, and clearly identify, the inductive hypothesis, in the form “assume that P(k)
is true for an arbitrary fixed integer k ≥ b.”
5. State what needs to be proved under the assumption that the inductive
hypothesis is true. That is, write out what P(k + 1) says.
6. Prove the statement P(k + 1) making use the assumption P(k). Be sure that your
proof is valid for all integers k with k ≥ b, taking care that the proof works for small
values of k, including k = b.
7. Clearly identify the conclusion of the inductive step, such as by saying “this
completes the inductive step.”
8. After completing the basis step and the inductive step, state the conclusion,
namely, by mathematical induction, P(n) is true for all integers n with n ≥ b.
Strong Induction and
Well-Ordering
Section 5.2
Strong Induction
Strong Induction: To prove that P(n) is true for all positive
integers n, where P(n) is a propositional function, complete
two steps:
• Basis Step: Verify that the proposition P(1) is true.
• Inductive Step: Show the conditional statement

 P (1)  P ( 2 )   P ( k )  → P ( k + 1)
holds for all positive integers k.

Strong Induction is sometimes called

the second principle of mathematical
induction or complete induction.
Completion of the proof of the Fundamental Theorem of
Arithmetic
Example: Show that if n is an integer greater than 1, then n can be written as the product of
primes.
Solution: Let P(n) be the proposition that n can be written as a product of primes.
• BASIS STEP: P(2) is true since 2 itself is prime.
• INDUCTIVE STEP: The inductive hypothesis is P(j) is true for all integers j with 2 ≤ j ≤ k. To show
that P(k + 1) must be true under this assumption, two cases need to be considered:
• If k + 1 is prime, then P(k + 1) is true.
• Otherwise, k + 1 is composite and can be written as the product of two positive integers a
and b with 2 ≤ a ≤ b < k + 1. By the inductive hypothesis a and b can be written as the
product of primes and therefore k + 1 can also be written as the product of those primes.
Hence, it has been shown that every integer greater than 1 can be written as the product of
primes.
Proof using Strong Induction 2

Example: Prove that every amount of postage of 12 cents or more can be formed using just 4-cent
and 5-cent stamps.
The Pigeonhole Principle
Section 6.2
Section Summary 2

The Pigeonhole Principle

The Generalized Pigeonhole Principle
The Pigeonhole Principle 1

If a flock of 20 pigeons roosts in a set of 19 pigeonholes, one of

the pigeonholes must have more than 1 pigeon.

Pigeonhole Principle: If k is a positive integer and k + 1 objects are placed into k boxes, then at
least one box contains two or more objects.

Proof: We use a proof by contraposition. Suppose none of the k boxes has more than one object.
Then the total number of objects would be at most k. This contradicts the statement that we have
k + 1 objects.
Jump to long description
Show that if five integers are selected from the first eight positive integers, there
must be a pair of these integers with a sum equal to 9.
During a month with 30 days, a baseball team plays at least one game a day, but no
more than 45 games. Show that there must be a period of some number of
consecutive days during which the team must play exactly 14 games.
The Generalized Pigeonhole Principle 1

The Generalized Pigeonhole Principle: If N objects are placed into k boxes, then there is at
least one box containing at least ⌈N/k⌉ objects.
Proof: We use a proof by contraposition. Suppose that none of the boxes contains more
than ⌈N/k⌉ − 1 objects. Then the total number of objects is at most

N    N  
k  − 1 < k   k + 1 − 1 = N ,
 k     
where the inequality ⌈N/k⌉ < ⌈N/k⌉ + 1 has been used. This is a
contradiction because there are a total of N objects.
Example: Among 100 people there are at least
⌈100/12⌉ = 9 who were born in the same month.
The Generalized Pigeonhole Principle 2

Example: a) How many cards must be selected from a standard deck of 52 cards to
guarantee that at least three cards of the same suit are chosen?
b) How many must be selected to guarantee that at least three hearts are selected?

Solution: a) We assume four boxes; one for each suit. Using the generalized
pigeonhole principle, at least one box contains at least ⌈N/4⌉ cards. At least three
cards of one suit are selected if ⌈N/4⌉ ≥3. The smallest integer N such that ⌈N/4⌉ ≥3
is N = 2 ∙ 4 + 1 = 9.

b) A deck contains 13 hearts and 39 cards which are not hearts. So, if we select 41
cards, we may have 39 cards which are not hearts along with 2 hearts. However,
when we select 42 cards, we must have at least three hearts.
What is the minimum number of students required in a discrete mathematics class
to be sure that at least six will receive the same grade, if there are five possible
grades, A, B, C, D, and F?

Prove that among any group of seven people (men and women), there must be at
least 4 of the same gender.