Question and Answers Assignment | Buy assignments online

MAD 2104: Discrete Mathematics Spring 2019 Take Home EXAM 3

Answer the questions by showing all your work. Begin each new question in a separate page. Answers without complete work will not receive credits. This test is due on Tuesday,

April 23^rd, 2019 at the beginning of the class. Staple this page with your name at the beginning of your exam. Write your name in every page.

Name:

1. Show that if A and B are sets with |A| = |B|, then |P(A)| = |P(B)|.
2. Show that the set Z⁺ × Z⁺ is countable.
3. Prove that the set of all (infinite) sequences of 0’s and 1’s (i.e: infinite bit strings) is uncountable. Hint: Use Cantor’s Diagonal Argument.

1. Use mathematical induction to prove that 1 for all integers n ≥ 1.
2. Prove that 21 divides 4ⁿ⁺¹ + 5²ⁿ⁻¹ whenever n is a positive integer.
3. Use mathematical induction to show that given a set of n+1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.
4. Consider this variation of the game of Nim. The game begins with n Two players take turns removing matches, one, two, or three at a time. The player removing the last match loses. Use strong induction to show that if each player plays the best strategy possible, the first player wins if n = 4j,4j + 2, or 4j + 3 for some nonnegative integer j and the second player wins in the remaining case when n = 4j + 1 for some nonnegative integer j.
5. Let f_nrepresent the n^th Fibonacci number. Show that f_n+1f_n−1 −f_n² = (−1)ⁿwhen n is a positive integer.
6. How many strings of eight uppercase English letters are there (a) that have the letter X, if letters can be repeated?
   • that start with X, if no letter can be repeated?
   • that do not have the letters B and O next to each other? That is, the letters BO and OB cannot appear in the string.
7. How many ways are there to seat four of a group of 10 people around a circular table where two seatings are considered the same when everyone has the same immediate left and immediate right neighbor?

1