Mathematical InductionClimbing an Infinite LadderPrinciple Mathematical InductionWarningExampleExampleExampleExampleExampleExampleThe Number of Subsets of a Finite SetThe Number of Subsets of a Finite SetDeMorgan for IntersectionDeMorgan for IntersectionDeMorgan for IntersectionCreative Uses of Mathematical InductionCreative Uses of Mathematical InductionStrong InductionStrong InductionExistence of Prime FactorizationExistence of Prime FactorizationExistence of Prime FactorizationWinning StrategyWinning StrategyWinning StrategyIntro to Discrete StructuresLecture 14Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 14 – p. 1/42Mathematical InductionMathematical induction is based on the rule of inference1. 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/42Climbing an Infinite Ladder1. We can reach the first rung of the ladder.2. If we can reach a particular rung of the ladder, then wecan reach the next rung of the ladder.3. Therefore, we can reach any rung of the ladder.Intro to Discrete StructuresLecture 14 – p. 3/42Principle Mathematical InductionTo prove that P (n) is true for all natural numbers n, whereP (n) is a propositional function, we complete two steps:Basis step: We verify that P (1) is true.We show that the conditional statementP (k) → P (k + 1)is true for all natural numbers k.Intro to Discrete StructuresLecture 14 – p. 4/42WarningIn a proof of mathematical induction is is not assumedthat 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 ofbegging the question, or circular reasoning.Intro to Discrete StructuresLecture 14 – p. 5/42ExampleExample: Show thatnXi=1i =n(n + 1)2.Intro to Discrete StructuresLecture 14 – p. 6/42ExampleIntro to Discrete StructuresLecture 14 – p. 7/42ExampleExample 2: Conjecture a formula for the sum of the first npositive integers. Then prove your conjecture usingmathematical induction.Intro to Discrete StructuresLecture 14 – p. 8/42ExampleIntro to Discrete StructuresLecture 14 – p. 9/42ExampleFind a formula fornXj=1(−1)jjIntro to Discrete StructuresLecture 14 – p. 10/42ExampleIntro to Discrete StructuresLecture 14 – p. 11/42The Number of Subsets of a Finite SetIntro to Discrete StructuresLecture 14 – p. 12/42The Number of Subsets of a Finite SetIntro to Discrete StructuresLecture 14 – p. 13/42DeMorgan for IntersectionExample 10: Proven\j=1Aj=n[j=1Ajwhenever A1, A2, . . . , Anare subset of a universal U andn ≥ 2.Intro to Discrete StructuresLecture 14 – p. 14/42DeMorgan for IntersectionIntro to Discrete StructuresLecture 14 – p. 15/42DeMorgan for IntersectionIntro to Discrete StructuresLecture 14 – p. 16/42Creative Uses of Mathematical InductionExample: Show that every 2n× 2ncheckerboard with onesquare removed can be tiled using L-shaped triominoes.Intro to Discrete StructuresLecture 14 – p. 17/42Creative Uses of Mathematical InductionIntro to Discrete StructuresLecture 14 – p. 18/42Strong InductionStrong induction is based on the rule of inference1. P (1)2. ∀k (∧kj=1P (j) → P (k + 1))3. ∴ ∀nP (n)which is true for the domain of natural numbers N.Intro to Discrete StructuresLecture 14 – p. 19/42Strong InductionTo prove that P (n) is true for all natural numbers n, whereP (n) is a propositional function, we complete two steps:Basis step: We verify that P (1) is true.We show that the conditional statementk^j=1P (j) → P (k + 1)is true for all natural numbers k.Intro to Discrete StructuresLecture 14 – p. 20/42Existence of Prime FactorizationExample: Show that if n is an integer greater than 1, then ncan be written as the product of primes.Intro to Discrete StructuresLecture 14 – p. 21/42Existence of Prime FactorizationIntro to Discrete StructuresLecture 14 – p. 22/42Existence of Prime FactorizationExample 2: Show that if n is an integer greater than 1, thenn can be written as the product of primes.Intro to Discrete StructuresLecture 14 – p. 23/42Winning StrategyExample 3:Intro to Discrete StructuresLecture 14 – p. 24/42Winning StrategyIntro to Discrete StructuresLecture 14 – p. 25/42Winning StrategyIntro to Discrete StructuresLecture 14 – p. 26/42Intro to Discrete StructuresLecture 14 – p. 27/42Intro to Discrete StructuresLecture 14 – p. 28/42Intro to Discrete StructuresLecture 14 – p. 29/42Intro to Discrete StructuresLecture 14 – p. 30/42Intro to Discrete StructuresLecture 14 – p. 31/42Intro to Discrete StructuresLecture 14 – p. 32/42Intro to Discrete StructuresLecture 14 – p. 33/42Intro to Discrete StructuresLecture 14 – p. 34/42Intro to Discrete StructuresLecture 14 – p. 35/42Intro to Discrete StructuresLecture 14 – p. 36/42Intro to Discrete StructuresLecture 14 – p. 37/42Intro to Discrete StructuresLecture 14 – p. 38/42Intro to Discrete StructuresLecture 14 – p. 39/42Intro to Discrete StructuresLecture 14 – p. 40/42Intro to Discrete StructuresLecture 14 – p. 41/42Intro to Discrete StructuresLecture 14 – p.
View Full Document
Unlocking...