Answer Happy

4. Let S be the set of positive integers defined recursively by Basis step: 4 ES Recursive step: x ES — 2x +1 ES No integers are in S other than those derived from the basis and the recursive steps. (a) [3 points] List the elements of S produced by the first three applications of the recursive rule. Show your work. (b) [5 points] Using structural induction, prove that for every integer x in S. x mod 5 = 4. You should show both the basis step and the inductive step of the proof. 5. [5 points] Give a recursive algorithm in pseudocode for computing the sum of the cubes of the first n odd positive integers. Use the header below and complete the body of the procedure. procedure sumcubes(n: positive integer) 6. [3 x 4 = 12 points] In questions below, suppose you have 12 books (6 novels, 4 history books, and 2 math books). Assume that all 12 books are different. (a) In how many ways can you get a bunch of 5 books to give to a friend? (b) In how many ways can you get a bunch of 2 history books and 5 novels to give to a friend? (c) In how many ways can you put the 12 books in a row on a shelf if the novels are on the left, the math books are in the middle, and the history books are on the right? (d) In how many ways can you get a bunch of 5 books including at least 3 novels to give to a friend? 7. [4 points] Each locker in the UH recreation center is labeled with an uppercase letter followed by two digits. At UH, there are 500 students who need lockers. What is the largest value N such that at least N students must necessarily share a locker? Justify your answer.