Outline of Intro to Discrete Exam #1 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. 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 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.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'tmention it in the review, I won't put this material on the firstexam. However, I need to test on it, so it will be included on thesecond exam.Reading from TextbookCounting & Binomial Theorem: 1.1 - 1.4Mathematical Induction: 4.1 - 4.2Number Theory: 4.3 - 4.5What to Study1) 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 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
View Full Document
Unlocking...