Outline of Intro to Discrete Exam 2 Topics I Counting a Addition Principle b Multiplication Principle c Subtraction Principle d Permutation of k object out of n e Permutations with repetition f Combination g Combinations with Repetition h Some Tricks i Subtracting from whole ii Using the binomial theorem 1 1 n 2n for example iii Super Letter idea for permuation problems iv Placing objects that must belong in certain places then counting the possible locations of the other objects v Visualizing what needs to be counted II Binomial Theorem a Derivation from counting principles b Don t forget negative signs c Don t forget parenthesis d Determine how to solve for the coefficient to xk III Mathematical Induction a Base Case b Inductive Hypothesis c Inductive Step d Summation Rules e Not all induction problems use summations f How to deal with inequalities g Strong Induction IV Number Theory a Division Algorithm b Euclid s Algorithm c Extended Euclid s Algorithm d Pi notation e Fundamental Thm of Algebra f Least Common Multiple LCM g Connection between LCM and GCD h Proof that 2 is irrational Sample Questions from Spring 2001 Final Exam 1 Use induction to prove that 64 32n 8n 1 for all integers n 0 2 10 pts Let c be an integer such that 3 c Prove that c 1 3 1 mod 9 3 Prove the following inequality for all positive integers n 2n log i n 1 2 2 n 1 i 1 Hint Remember that log2 2x y x when x is a positive integer and y is a non negative integer such that y 2x 4 10 pts In a gumball machine there are 32 red gumballs 14 green gumballs 30 white gumballs and 5 purple gumballs A devoted customer purchases 10 gumballs How many combinations of gumballs can the customer receive Remember the order in which you receive the gumballs does not matter Only the total set of 10 gumballs matters Note Other questions will be added tomorrow
View Full Document
Unlocking...