solve question 2 please Discrete Mathematics Solve SEVEN problems from #1-9 1 Fi
ID: 3283235 • Letter: S
Question
solve question 2 please
Discrete Mathematics Solve SEVEN problems from #1-9 1 Final Examination Review 10 pts. each 1 Spring 2018 1 . Solve : xn+1 = 1 1xn-10 Xn-l , XO-2, x 2. Prove that 2"> 50n+1 for n2 7 3. In how many ways can a. 80 identical one-inch toothpicks be distributed among 46 people ? b. one form distinct 11-letter words by permuting the letters of DERANGEMENT? c. d. an edge be selected from the complete bipartite graph K 10, 15? construct a permutations of 10 objects that fix 7 of them 4. Let C(nk) denote the coefficient ofXk n the expansion of (1+x)" a. For which n and k will C(n, k) C(30, 12)+ C(30, 13) b. Find C(40,2)42 C(40,3)43+...+C(40,38)438 [BE CAREFUL!] e. Find the order of growth of C(n, n-2) as n increases 5. a. Suppose that k people select a number from 1 to 100. How large must k be in order to insure that at least 10 people picked the same number ? b. In how many ways can a function be constructed from (a, b, c to 12,4,6, 8,? c. Find the order of growth of the sum 33 +63+93 123. (3n) as n ncreases 6. Let X la,b,c,d) and let Y (1,2,3). Find the EXPLICIT number of (a) surjections from X ? Y (b) injections from Y ? X (c) maps ( functions) fromxpower set of Y 7. (a) Find the number of permutations of 10 objects that fix 7 of them (b) Find 2Y mod 17 8. There are 1000 students in college XYZ. Suppose 240 take BIO, 240 take MATH and 240 take ENGLISH. If 50 take BIO and MATH, 70 take MATH and ENGLISH, 60 take BIO and ENGLISH, and 20 take all three subjects, then how many students take none of these three subjects? Use the inclusion-exclusion method 9. Let S be the set of strings of length 5 in the characters 0, 1, 2,.., 9. Define an equivalence relation ~on S as follows: Two strings sl and s2 are equivalent, s1 s2, if they are identical with each other in their first and last digits. (a) How many members does the equivalence class [12345] have? (b) How many distinct equivalence classes exist?Explanation / Answer
2. Let P(n) be the statement , P(n) : 2n > 50n + 1 for all n >= 7
Basic step : for n = 7, we have, 27 = 128 > 50.2 + 1 = 101, hence P(7) is true.
Induction Hypothesis : suppose P(n) is true for some m >= 7
Then, 2m >= 50m + 1,
so, 2.2m >= 100m + 2 > 50(m+1) + 1 (since, m >= 7, so, 50m > 50)
Hence, 2m+1 >= 50(m+1) + 1
Hence P(m+1) is true whenever P(m) is true.
Hence P(n) is true for all n >= 7
Hence proved.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.