Discrete Mathematics Math 2305 Exam II - 25 April 2024 PDF

ROSTER LAST NAME: FIRST NAME: SECTION TIME: ESTIMATED IN-CLASS ATTENDANCE COUNT /25 classes: (Note: only include in-person, in-seat attendance, do not include excused absences)...

ROSTER LAST NAME: FIRST NAME: SECTION TIME: ESTIMATED IN-CLASS ATTENDANCE COUNT /25 classes: (Note: only include in-person, in-seat attendance, do not include excused absences) DISCRETE MATHEMATICS MATH 2305 EXAM II Thursday, 25 APRIL, 2024 CRITICAL EXAM INFORMATION – CLOSED-BOOK EXAM. No notes, internet, calculator, programs, communication, etc... – Work smartly. Do not spend too much time on any one problem. If you get stuck, move on and come back later. – READ EACH QUESTION CAREFULLY. New combinations of questions or variations to previous homework questions are likely present. – If you need extra space to write your solution, write on the back of the previous page or on a blank page and mark your problem number with “continued” or “con’t” – The exam is scored out of 100 points total (plus possible extra credit 10 points). – Multiple choice questions have only one correct answer. Questions may be numbered differently from exam-to-exam. 1  DISCRETE MATHEMATICS MATH 2305 25 APRIL 2024 EXAM II 1 Choose the single best answer to the following questions. 6 pts. each, 60 points total Note: There is only one correct answer for each question; there is no penalty for guessing. Clearly mark your answer. n n 3j , and 2j , where n is an integer and n > 0. Then P P 1. Let S1 = S2 = j=0 j=0 n (3 · 2)j P a) S1 + S2 = j=0 n (3 + 2)j P b) S1 + S2 = j=0 n (3j + 2j ) P c) S1 + S2 = j=0 d) none of the above n (2 · 3j + 3 · 2j ), where n is an integer and n > 0. P 2. Consider the sum of terms given by: j=0 This sum of terms is: a) an arithmetic progression b) a geometric progression c) both a) and b) above d) none of the above 3. If a set A is countably infinite, then a) there exists an injection from A to the set of natural numbers N b) there exists a surjection from the set of natural numbers N to A c) there exists a bijection between A and the set of natural numbers N d) all of the above e) none of the above 4. Let N = {1, 2, 3,...}, Z = {0, ±1, ±2, ±3,...} (i.e. N is the set of natural numbers and Z the integers), and recall if A is a set, |A| is the cardinality of A. a) |Z| > |N|, where Z is uncountably infinite and N is countably infinite b) |Z| > |N|, and both are uncountably infinite c) |Z| = |N|, and both are countably infinite d) none of the above 5. Let P (n) be a propositional function for positive integers n. To prove P (n) by mathematical induction, the inductive step is best described as: a) ∀k(P (k) =⇒ P (k + 1)) for all positive integers k b) P (1) =⇒ P (k) =⇒ P (k + 1) =⇒ P (n) for all positive integers k, n c) P (1) =⇒ ∀k(P (k) =⇒ P (k + 1)) =⇒ P (n) for all positive integers k, n d) (P (1) ∧ (P (k) ∧ P (k + 1)) =⇒ P (n) for all positive integers k, n 2  DISCRETE MATHEMATICS MATH 2305 25 APRIL 2024 EXAM II For the following questions, let P (n, r), C(n, r) be the number of permutations and combinations, respectively, of a set with n elements taken r at a time, where r ≤ n and both n, r are non-negative integers (i.e., n, r ≥ 0). 6. If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways, then there are how many ways to do the task? a) n1 + n2 by the sum rule b) n1 · n2 by the product rule c) n1 ! · n2 ! by the product rule d) none of the above 7. Consider the English alphabet, which consists of 26 letters, and let upper-case and lower-case letters be distinguished (for example, the letter ‘A’ and ‘a’ are different letters for our purposes, and there are thus 2 x 26 = 52 possible unique letters). In how many different ways can a 5-letter password be chosen if none of the 52 letters can be repeated? a) 552 b) 525 c) 52!/47! d) 52!/46! e) none of the above 8. How many one-to-one (injective) functions are there from a set A to itself, where |A| = 5? a) 5! b) 55 c) 5·5 d) 5+5 e) none of the above 9. How many bit strings of length 10 have no consecutive sequence of 9 1’s? a) 29 − 2 b) 210 − 3 c) 210 − C(10, 1) d) none of the above 10. The number of ways to choose an unordered team of 40 students to show up to class out of 89 students registered is: a) P (40, 89) b) C(89, 49) c) 89! − 40! d) none of the above 3  DISCRETE MATHEMATICS MATH 2305 25 APRIL 2024 EXAM II 20 points total 2 Induction 2.1 Prove using induction: for any n ∈ {1, 2,...}, n(n + 1) 1 + 2 + 3 +... + n = 2 2.2 Prove using induction: for any n ∈ {0, 1, 2,...}, 1 + 2 + 22 +... + 2n = 2n+1 − 1 4  DISCRETE MATHEMATICS MATH 2305 25 APRIL 2024 EXAM II 20 points total 3 Counting + 3.1 [10 pts.] Is the set of positive odd integers Zodd = {1, 3, 5,...} countably infinite? If so, give an appropriate function that supports this claim. 3.2 [5 pts.] How many different ways are there to seat three people around a circular table (with only 3 chairs), where two seatings are considered the same when each person has the same left neighbor and the same right neighbor? 3.3 [5 pts.] How many bit strings of length 10 either begin with six 0s or end with five 0s (or both)? 5  DISCRETE MATHEMATICS MATH 2305 25 APRIL 2024 EXAM II 4 EXTRA CREDIT PROBLEMS: 10 points total Sums of Geometric Progressions: Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term a and common ratio r, where a, r are real numbers such that r ̸= 1, and n is a positive integer: n X arn+1 − a arj = j=0 r−1 Note: you must prove this by induction to receive credit. Proof: END OF EXAM 6