DeMorgan 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 StrategyWell-Ordering PropertyDivision AlgorithmDivision AlgorithmCycles in Round-Robin TournamentCycles in Round-Robin TournamentRecursive Definitions & Structural InductionRecursively Defined FunctionsFibonacci numbersGrowth of the Fibonacci NumbersGrowth of the Fibonacci NumbersRecursively Defined Sets and StructuresWell-Formed FormulaeStructural InductionStructural InductionIntro to Discrete StructuresLecture 15Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 15 – p. 1/35DeMorgan for IntersectionExample 10: Proven\j=1Aj=n[j=1Ajwhenever A1, A2, . . . , Anare subset of a universal U andn ≥ 2.Intro to Discrete StructuresLecture 15 – p. 2/35DeMorgan for IntersectionIntro to Discrete StructuresLecture 15 – p. 3/35DeMorgan for IntersectionIntro to Discrete StructuresLecture 15 – p. 4/35Creative Uses of Mathematical InductionExample: Show that every 2n× 2ncheckerboard with onesquare removed can be tiled using L-shaped triominoes.Intro to Discrete StructuresLecture 15 – p. 5/35Creative Uses of Mathematical InductionIntro to Discrete StructuresLecture 15 – p. 6/35Strong 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 15 – p. 7/35Strong 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 15 – p. 8/35Existence 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 15 – p. 9/35Existence of Prime FactorizationIntro to Discrete StructuresLecture 15 – p. 10/35Existence 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 15 – p. 11/35Winning StrategyExample 3:Intro to Discrete StructuresLecture 15 – p. 12/35Winning StrategyIntro to Discrete StructuresLecture 15 – p. 13/35Winning StrategyIntro to Discrete StructuresLecture 15 – p. 14/35Well-Ordering PropertyThe validity of both the principle of mathematical inductionand strong induction follows from a fundamental axiom ofset of integers, the well-ordering property.THE WELL-ORDERING PROPERTY: Every nonempty setof nonnegative integers has a least element.Intro to Discrete StructuresLecture 15 – p. 15/35Division AlgorithmExample 5: Use the well-ordering property to prove thedivision algorithm.Intro to Discrete StructuresLecture 15 – p. 16/35Division AlgorithmIntro to Discrete StructuresLecture 15 – p. 17/35Cycles in Round-Robin TournamentExample 6:Intro to Discrete StructuresLecture 15 – p. 18/35Cycles in Round-Robin TournamentIntro to Discrete StructuresLecture 15 – p. 19/35Recursive Definitions & Structural InductionSometimes it is difficult to define an object explicitly.However, it may be easy to define this object in terms ofitself. This process is called recursion.Intro to Discrete StructuresLecture 15 – p. 20/35Recursively Defined FunctionsWe use two steps to define a function with the set ofnonnegative integers as its domain:Basis Step: Specify the value of the function at zero.Recursive Step: Give a rule for finding its valuesfrom its values at smaller integers.Example 1: Suppose that is recursively defined byf(0) = 3 ,f(n + 1) = 2f(n) + 3 .Find f(1), f(2), f(3), and f(4).Intro to Discrete StructuresLecture 15 – p. 21/35Fibonacci numbersDefinition 1: The Fibonacci numbers f0, f1, f2, ...aredefined by the equation f0, f1= 1, andfn= fn+1+ fn+2for n = 2, 3, 4, . . ..Intro to Discrete StructuresLecture 15 – p. 22/35Growth of the Fibonacci NumbersExample 6: Show that whenever n ≥ 3, fn> αn−2, whereα = (1 +√5)/2.Intro to Discrete StructuresLecture 15 – p. 23/35Growth of the Fibonacci NumbersIntro to Discrete StructuresLecture 15 – p. 24/35Recursively Defined Sets and StructuresExample 7: Consider the subset S of integers defined byBasis step: 3 ∈ S.Recursive step: If x ∈ S and y ∈ S, then x + y ∈ S.Intro to Discrete StructuresLecture 15 – p. 25/35Well-Formed FormulaeExample 10: We can define the set of well-formed formulaefor compound statement forms involving T, F, propositionalvariables, and operators from the set {¬, ∧, ∨, →, ↔}.Basis step: T, F, and, s, where s is a propositionalvariable, are well-formed formulae.Recursive step: If E and F are well-formed formulae,then (¬E), (E ∧ F ), (E ∨ F ), (E → F ), and (E ↔ F ) arewell-formed.Intro to Discrete StructuresLecture 15 – p. 26/35Structural InductionA proof by structural induction consists of two parts:Show that the result holds for all elements in thebasis step of the recursive definition.Show that if the statement is true for each of theelements used to construct new elements in therecursive step of the definition, the result holds forthese new elements.The validity of structural induction follows from theprinciple of mathematical induction of nonnegativeintegers. To see this, let P (n) state that this claim is truefor all elements that are generated by n or fewapplications of these rules.Intro to Discrete StructuresLecture 15 – p. 27/35Structural InductionExample 13: Show that every well-formed formulae forcompound propositions contains an equal number of leftand right parentheses.Intro to Discrete StructuresLecture 15 – p. 28/35Intro to Discrete StructuresLecture 15 – p. 29/35Intro to Discrete StructuresLecture 15 – p. 30/35Intro to Discrete StructuresLecture 15 – p. 31/35Intro to Discrete StructuresLecture 15 – p. 32/35Intro to Discrete StructuresLecture 15 – p. 33/35Intro to Discrete StructuresLecture 15 – p. 34/35Intro to Discrete StructuresLecture 15 – p.
View Full Document
Unlocking...