Outline of Intro to Discrete Exam #2 TopicsI. 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 inequalitiesg. Strong InductionIV. 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 Exam1) Use induction to prove that 64 | (32n – 8n – 1) for all integersn 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: 12)1(log212ninin (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, 14green gumballs, 30 white gumballs, and 5 purple gumballs. Adevoted customer purchases 10 gumballs. How manycombinations of gumballs can the customer receive?(Remember the order in which you receive the gumballs doesnot matter. Only the total set of 10 gumballs matters.)Note: Other questions will be added
View Full Document