Outline of Intro to Discrete Exam 1 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 Super Letter idea for permuation problems iii Placing objects that must belong in certain places then counting the possible locations of the other objects iv 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 Note In covering this in class I missed the following material Probability and sections 3 4 3 7 in the text Since some students won t study for this because I didn t mention it in the review I won t put this material on the first exam However I need to test on it so it will be included on the second exam Reading from Textbook Counting Binomial Theorem 1 1 1 4 Mathematical Induction 4 1 4 2 Number Theory 4 3 4 5 What to Study 1 Read the notes 2 Read the textbook I ve stuck fairly closely to it throughout these sections 3 Practice problems in the textbook 4 Look over past quizzes 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
View Full Document
Unlocking...