CMSC 250 Discrete StructuresSummationsPropertiesUsing the PropertiesMathematical InductionInductive ProofInductive Proofs Must HaveSlide 8Slide 9Another ExampleSetsSet Operations Formal Definitions and Venn DiagramsProcedural Versions of Set DefinitionsProperties of Sets (Theorems 5.2.1 & 5.2.2)Prove A=CDoes A=DHW10, Problem 2CountingProve: # elements in list = n – m + 1How many in list divisible by somethingMultiplication RuleSlide 22Permutation ExampleDifference Rule FormallyAddition Rule FormallyInclusion/Exclusion Ruler-PermutationsPermutationsPermutation w/ Repeated ElementsCombinationsCombinations with RepititionBinomial TheoremCMSC 250Discrete StructuresExam 2 ReviewJanuary 14, 2019 Exam 2 Review 2SummationsWhat is next in the series …General formula for a seriesIdentical seriesSummation and product notationProperties (splitting/merging, distribution)Change of variablesApplications (indexing, loops, algorithms)______,1625,916,49,4 1,122 kkkak7171601111kjkkjk1,1 kkkak2,1 iiibi612kkkk251January 14, 2019 Exam 2 Review 3PropertiesMerging and SplittingDistribution nmkkknmkknmkkbaba kknmkknmkknmkbaba nmkknmkkacacnikkimkknmkkaaa1knikkimkknmkaaa1January 14, 2019 Exam 2 Review 4Using the Properties1;1 kbkakknmkknmkkba 2nmkknmkkbaJanuary 14, 2019 Exam 2 Review 5Mathematical InductionDefinition–Used to verify a property of a sequence–Formal definition (next slide)What proofs must haveWe proved: –General summation/product –Inequalities –Strong inductionMisc–Recurrence relations–Quotient remainder theorem–Correctness of algorithms (Loop Invariant Theorem)ninni12)1(1,,,1001raararZnRaRrnnjjJanuary 14, 2019 Exam 2 Review 6Inductive ProofLet P(n) be a property that is defined for integers n , and let a be a fixed integer. Suppose the following two statements are true.–P(a) is true.–For all integers k ≥ a, if P(k) is true then P(k+1) is true.Then the statement for all integers n ≥ a, P(n) is true.January 14, 2019 Exam 2 Review 7Inductive Proofs Must HaveBase Case (value)–Prove base case is trueInductive Hypothesis (value)–State what will be assumed in this proofInductive Step (value)–ShowState what will be proven in the next section–ProofProve what is stated in the show portionMust use the Inductive Hypothesis sometimeJanuary 14, 2019 Exam 2 Review 8Prove this statement:Base Case (n=3):Inductive Hypothesis (n=k):Inductive Step (n=k+1):Show: Proof:7161)3(2: LHS82:3RHSkk 212 121)1(2kkRHSLHS nnZn 212,3January 14, 2019 Exam 2 Review 9Prove this statement:Inductive Step (n=k+1):Show: Proof:New goal:Which is true since k≥3.So and 222122212212211 kkkkkk 12112kknnZn 212,3 12112kk 2224twobyMultiply212 kkkkIH24212 kkkk 412 k21 k212224212 kkkJanuary 14, 2019 Exam 2 Review 10Another ExampleFor all integers n ≥ 1, 1232nJanuary 14, 2019 Exam 2 Review 11SetsSet–Notation – versus –Definitions – Subset, proper subset, partitions/disjoint sets–Operations (, , –, ’, )–Properties and inference rules–Venn diagrams–Empty set propertiesProofs–Element argument, set equality–Propositional logic / predicate calculus–Inference rules–Counterexample–Types – generic particular, induction, contra’s, CWRussell’s Paradox (The Barber’s Puzzle) & Halting ProblemJanuary 14, 2019 Exam 2 Review 12Set OperationsFormal Definitions and Venn DiagramsUnion:Intersection:Complement:Difference:}|{ BxAxUxBA }|{ BxAxUxBA }|{ BxAxUxBA }|{' AxUxAAc'BABA January 14, 2019 Exam 2 Review 13Procedural Versions of Set DefinitionsLet X and Y be subsets of a universal set U and suppose x and y are elements of U.1. x(X Y) xX or xY 2. x(X Y) xX and xY 3. x(X –Y) xX and xY 4. xXc xX 5. (x ,y)(XY ) xX and yYJanuary 14, 2019 Exam 2 Review 14Properties of Sets (Theorems 5.2.1 & 5.2.2)Inclusion TransitivityDeMorgan’s for ComplementDistribution of union and intersectionABA BBA BAA BAB CACBBA '')'( BABA '')'( BABA )()()( CABACBA )()()( CABACBA January 14, 2019 Exam 2 Review 15Prove A=CA={nZ | pZ, n = 2p}C={mZ | qZ, m = 2q-2}January 14, 2019 Exam 2 Review 16Does A=DA={xZ | pZ, x = 2p}D={yZ | qZ, y = 3q+1}Easy to disprove universal statements!January 14, 2019 Exam 2 Review 17HW10, Problem 2Did yesterday in class …January 14, 2019 Exam 2 Review 18CountingCounting elements in a list–How many in list are divisible by xProbability – likelihood of an eventPermutations – with and without repetitionMultiplication rule–Tournament play–Rearranging letters in words–Where it doesn’t workDifference rule – If A is a finite set and BA, then n(A – B) = n(A) – n(B)Addition rule – If A1 A2 A3 … Ak=A and A1, A2 , A3,…,Ak are pairwise disjoint, then n(A) = n(A1) + n(A2) + n(A3) + … + n(Ak)Inclusion/exclusion ruleCombinations – with and without repetition, categoriesBinomial theorem (Pascal’s Triangle))()()(SnEnEP )!(!),(rnnPrnPnr!)!(!!),(),(rrnnrrnPrnrnCrnr 1niic1)(January 14, 2019 Exam 2 Review 19Prove: # elements in list = n – m + 1Base case (List of size 1, x=y)–y – x + 1 = y – y + 1 (by substitution) = 1IH (generic x, y=k [where x k])–Assume size of list x to k, is k – x + 1IS–Show size of list x to k + 1, is (k + 1) – x + 1–ProveSplit into two lists …January 14, 2019 Exam 2 Review 20How many in list divisible by somethingHow
View Full Document
Unlocking...