CMSC 250 Discrete Structures Exam 2 Review Summations What is next in the series General formula for a series Identical series k ak k 1 k 1 9 16 25 4 4 9 16 2 k 1 ak k2 i 1 bi i 2 i 6 Summation and product notation 2 k k 1 Properties splitting merging distribution 6 7 7 k 1 5 2k k 1 1 1 1 k 0 k 1 j 1 j k 1 k Change of variables Applications indexing loops algorithms January 14 2019 Exam 2 Review 2 Properties Merging n n and Splitting n a b a k k m k k m k bk k m n a a k k m n n n ak bk ak bk k m k m k m i k m k n a k k i 1 i n ak ak ak k m k m k i 1 n Distribution n n k m k m c ak c ak January 14 2019 Exam 2 Review 3 Using the Properties ak k 1 bk k 1 n a k m n k 2 bk k m ak bk k m k m n January 14 2019 n Exam 2 Review 4 Mathematical Induction Definition Used to verify a property of a sequence Formal definition next slide What proofs must have We proved n i n n 1 2 General summation product i 1 n 1 n Inequalities ar a r R 1 a R n Z 0 ar j Strong induction r 1 j 0 Misc Recurrence relations Quotient remainder theorem Correctness of algorithms Loop Invariant Theorem January 14 2019 Exam 2 Review 5 Inductive Proof Let 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 6 Inductive Proofs Must Have Base Case value Prove base case is true Inductive Hypothesis value State what will be assumed in this proof Inductive Step value Show State what will be proven in the next section Proof Prove what is stated in the show portion Must use the Inductive Hypothesis sometime January 14 2019 Exam 2 Review 7 Prove this statement n Z 3 2n 1 2 n LHS 2 3 1 6 1 7 Base Case n 3 3 RHS 2 8 LHS RHS Inductive Hypothesis n k 2k 1 2 k Inductive Step n k 1 k 1 Show 2 k 1 1 2 Proof January 14 2019 Exam 2 Review 8 Prove this statement n Z 3 2n 1 2 n Inductive Step n k 1 k 1 2 k 1 1 2 Show Proof 2k 2 1 2 k 1 2k 1 2 2 k 1 2k 1 2 2 k 2 IH 2 k 1 2 k Multiply by two 4k 2 2 k 2 1 2 4k 2 2k 1 4k 1 2k New goal 2k 1 k 2 Which is true since k 3 k So 2k 1 2 4k 2 2 January 14 2019 2 Exam 2 Review k 1 1 2 and 2 9 k 1 Another Example For all integers n 1 3 January 14 2019 Exam 2 Review 2 2n 1 10 Sets Set Proofs Notation versus Definitions Subset proper subset partitions disjoint sets Operations Properties and inference rules Venn diagrams Empty set properties Element argument set equality Propositional logic predicate calculus Inference rules Counterexample Types generic particular induction contra s CW Russell s Paradox The Barber s Puzzle Halting Problem January 14 2019 Exam 2 Review 11 Set Operations Formal Definitions and Venn Diagrams Union A B x U x A x B Intersection A B x U x A x B Complement c A A x U x A Difference A B x U x A x B A B A B January 14 2019 Exam 2 Review 12 Procedural Versions of Set Definitions Let X and Y be subsets of a universal set U and suppose x and y are elements of U 1 2 3 4 5 x X Y x X or x Y x X Y x X and x Y x X Y x X and x Y x Xc x X x y X Y x X and y Y January 14 2019 Exam 2 Review 13 Properties of Sets Theorems 5 2 1 5 2 2 Inclusion A B A A A B A B B B A B Transitivity A B B C A C DeMorgan s for Complement Distribution of union and intersection A B A B A B A B A B C A B A C A B C A B A C January 14 2019 Exam 2 Review 14 Prove A C A n Z p Z n 2p C m Z q Z m 2q 2 January 14 2019 Exam 2 Review 15 Does A D A x Z p Z x 2p D y Z q Z y 3q 1 Easy to disprove universal statements January 14 2019 Exam 2 Review 16 HW10 Problem 2 Did yesterday in class January 14 2019 Exam 2 Review 17 Counting P E Counting elements in a list How many in list are divisible by x Probability likelihood of an event Permutations with and without repetition n Multiplication rule c i Tournament play i 1 Rearranging letters in words Where it doesn t work P n r r P n n E n S n n r Difference rule If A is a finite set and B A then n A B n A n B Addition rule If A A A A A and A A A A are n P n r n Inclusion exclusion rule C n r r n r r r Combinations with and without repetition categories r n 1 Binomial theorem Pascal s Triangle 1 2 3 k 1 2 3 pairwise disjoint then n A n A1 n A2 n A3 n Ak k January 14 2019 Exam 2 Review r 18 Prove elements in list n m 1 Base case List of size 1 x y y x 1 y y 1 by substitution 1 IH generic x y k where x k Assume size of list x to k is k x 1 IS Show size of list x to k 1 is k 1 x 1 Prove Split into two lists January 14 2019 Exam 2 Review 19 How many in list divisible by something How many positive three digit integers are there this means only the ones that require 3 digits 999 100 1 900 How many three digit integers are divisible by 5 think about the definition of divisible by x y k Z y kx and then count the k s that work 100 101 102 103 104 105 106 994 995 996 997 998 999 20 5 21 5 199 5 count the integers between …
View Full Document
Unlocking...