Discrete Mathematics - Lecture 5.1 Mathematical Induction PDF

Preview

Summary

Discrete Mathematics - Lecture 5.1 Mathematical Induction...

Description

Math 3336 Section 5.1 Mathematical Induction • • • •

Mathematical Induction Examples of Proof by Mathematical Induction Mistaken Proofs by Mathematical Induction Guidelines for Proofs by Mathematical Induction

Suppose we have an infinite ladder: 1. We can reach the first rung of the ladder. 2. If we can reach a particular rung of the ladder, then we can reach the next rung. Page 1 of 8

Principle of Mathematical Ind complete these steps: • ow that • : Show

is true for

we

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. Important points about Mathematical Induction • Mathematical induction can be expressed as the rule of inference where the domain is the set of positive integers. )) → ∀n P(n) •

• •

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 In such a case, the basis step begins at l see examples of this soon. Mathematical Induction s not give insights on why a theorem works.

Example: Show that if

, then 1 + 2 + ⋯ + ฀ ฀ =

฀฀(฀฀+1) 2

.

Example: Conjecture a formula for the sum of the first n p the conjecture using mathematical induction.

Page 3 of 8

. Then prove

฀฀ ≥ 4.

Page 4 of 8

Example: Prove that ฀฀3 − ฀฀ is divisible by 3 whenever n is a

Page 5 of 8

.

Example: Use mathematical induction to prove that 7

Page 6 of 8

+1

is divisible by 57 for

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

Page 7 of 8

Mistaken Proofs by Mathematical Induction Example (All horses are white): Let ฀฀(฀฀): “All horses are the same color.” Basic Step: ฀฀(1) is true. Inductive Step: Assume that ฀฀(฀฀) is true, so that all horses in a set of ฀฀ horses are the same color. Consider any ฀ ฀ + 1 horses; number these as horses 1,

฀ ฀ + 1.

Now the first ฀฀ of these horses all must have the same color, and the last ฀฀ of these must have the same color. Because the set of the first ฀฀ and the last k overlap, all ฀ ฀ + 1 must have the same color. This shows that ฀฀(฀ ฀ + 1) is true and finishes the proof by induction.

Page 8 of 8...