Intro to Discrete Structures Lecture 14 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 14 p 1 42 Mathematical Induction Mathematical induction is based on the rule of inference 1 P 1 2 k P k P k 1 3 nP n which is true for the domain of natural numbers N Intro to Discrete StructuresLecture 14 p 2 42 Climbing 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 of the ladder 3 Therefore we can reach any rung of the ladder Intro to Discrete StructuresLecture 14 p 3 42 Principle Mathematical Induction To prove that P n is true for all natural numbers n where P n is a propositional function we complete two steps Basis step We verify that P 1 is true We show that the conditional statement P k P k 1 is true for all natural numbers k Intro to Discrete StructuresLecture 14 p 4 42 Warning In a proof of mathematical induction is is not assumed that P k is true for all k It is only shown that if it is assumed that P k is true then P k 1 is also true Thus a proof of mathematical induction is not a case of begging the question or circular reasoning Intro to Discrete StructuresLecture 14 p 5 42 Example Example Show that n X i 1 n n 1 i 2 Intro to Discrete StructuresLecture 14 p 6 42 Example Intro to Discrete StructuresLecture 14 p 7 42 Example Example 2 Conjecture a formula for the sum of the first n positive integers Then prove your conjecture using mathematical induction Intro to Discrete StructuresLecture 14 p 8 42 Example Intro to Discrete StructuresLecture 14 p 9 42 Example Find a formula for n X 1 j j j 1 Intro to Discrete StructuresLecture 14 p 10 42 Example Intro to Discrete StructuresLecture 14 p 11 42 The Number of Subsets of a Finite Set Intro to Discrete StructuresLecture 14 p 12 42 The Number of Subsets of a Finite Set Intro to Discrete StructuresLecture 14 p 13 42 DeMorgan for Intersection Example 10 Prove n j 1 Aj n Aj j 1 whenever A1 A2 An are subset of a universal U and n 2 Intro to Discrete StructuresLecture 14 p 14 42 DeMorgan for Intersection Intro to Discrete StructuresLecture 14 p 15 42 DeMorgan for Intersection Intro to Discrete StructuresLecture 14 p 16 42 Creative Uses of Mathematical Induction Example Show that every 2n 2n checkerboard with one square removed can be tiled using L shaped triominoes Intro to Discrete StructuresLecture 14 p 17 42 Creative Uses of Mathematical Induction Intro to Discrete StructuresLecture 14 p 18 42 Strong Induction Strong induction is based on the rule of inference 1 P 1 2 k kj 1 P j P k 1 3 nP n which is true for the domain of natural numbers N Intro to Discrete StructuresLecture 14 p 19 42 Strong Induction To prove that P n is true for all natural numbers n where P n is a propositional function we complete two steps Basis step We verify that P 1 is true We show that the conditional statement k P j P k 1 j 1 is true for all natural numbers k Intro to Discrete StructuresLecture 14 p 20 42 Existence of Prime Factorization Example Show that if n is an integer greater than 1 then n can be written as the product of primes Intro to Discrete StructuresLecture 14 p 21 42 Existence of Prime Factorization Intro to Discrete StructuresLecture 14 p 22 42 Existence of Prime Factorization Example 2 Show that if n is an integer greater than 1 then n can be written as the product of primes Intro to Discrete StructuresLecture 14 p 23 42 Winning Strategy Example 3 Intro to Discrete StructuresLecture 14 p 24 42 Winning Strategy Intro to Discrete StructuresLecture 14 p 25 42 Winning Strategy Intro to Discrete StructuresLecture 14 p 26 42 Intro to Discrete StructuresLecture 14 p 27 42 Intro to Discrete StructuresLecture 14 p 28 42 Intro to Discrete StructuresLecture 14 p 29 42 Intro to Discrete StructuresLecture 14 p 30 42 Intro to Discrete StructuresLecture 14 p 31 42 Intro to Discrete StructuresLecture 14 p 32 42 Intro to Discrete StructuresLecture 14 p 33 42 Intro to Discrete StructuresLecture 14 p 34 42 Intro to Discrete StructuresLecture 14 p 35 42 Intro to Discrete StructuresLecture 14 p 36 42 Intro to Discrete StructuresLecture 14 p 37 42 Intro to Discrete StructuresLecture 14 p 38 42 Intro to Discrete StructuresLecture 14 p 39 42 Intro to Discrete StructuresLecture 14 p 40 42 Intro to Discrete StructuresLecture 14 p 41 42 Intro to Discrete StructuresLecture 14 p 42 42
View Full Document
Unlocking...