## Exercises #### Section A.1 1. Determine each of the following 1. \[2.8\] 2. \[–10.42\] 3. \[4.2\] 4. \[–34.92\] 5. \[5.2–4.7\] 6. \[2π\] 2. Show that \[*n*\] = − \[–*n*\]. 3. Show that, for any real *x*,  4. Show that for any integers *a* > 0, *b* > 0, and *n*,  5. Write each of the following using summation (sigma) notation. 1. 2 + 4 + 6 + … + 2(99) + 2(100) 2. 2 + 4 + 6 + … + 2(*n* − 1) + 2*n* 3. 3 + 12 + 27 + … + 1200 6. Evaluate each of the following sums.  (*Hint*: You should see a pattern if you write the first two or three terms without simplification.)  #### Section A.2 1. Graph the function . What are the domain and range of this function? 2. Graph the function *f*(*x*) = (*x* − 2) / (*x* + 5). What are the domain and range of this function? 3. Graph the function *f*(*x*) = ⌊*x*⌋. What are the domain and range of this function? 4. Graph the function *f*(*x*) = ⌈*x*⌉. What are the domain and range of this function? #### Section A.3 1. Use mathematical induction to show that, for all integers *n* > 0,  2. Use mathematical induction to show that *n*2− *n* is even for any positive integer *n*. 3. Use mathematical induction to show that, for all integers *n* > 4, 2*n* > *n*2. 4. Use mathematical induction to show that, for all integers *n* > 0,  #### Section A.4 1. Prove that if *a* and *b* are both odd integers, *a* + *b* is an even integer. Is the reverse implication true? 2. Prove that *a* + *b* is an odd integer if and only if *a* and *b* are not both odd or both even integers. #### Section A.5 1. Determine each of the following. 1. log 1,000 2. log 100,000 3. log4 64 4.  5. log5 125 6. log 23 7. lg (16 × 8) 8. log (1,000/100,000) 9. 2lg 125 2. Graph *f* (*x*) = 2*x* and *g* (*x*) = lg *x* on the same coordinate system. 3. Give the values of *x* for which *x*2 + 6*x* + 12 > 8*x* + 20. 4. Give the values of *x* for which *x* > 500 lg *x*. 5. Show that *f* (*x*) = 23 lg *x* is not an exponential function. 6. Show that, for any positive integer *n*,  7. Find a formula for lg (*n*!) using Stirling's approximation for *n*!,  for large *n*. #### Section A.6 1. Let *U* = {2, 4, 5, 6, 8, 10, 12}, *S* = {2, 4, 5, 10}, and *T* = {2, 6, 8, 10}. (*U* is the universal set.) Determine each of the following. 1. *S* ∪ *T* 2. *S* ∩ *T* 3. *S* − *T* 4. *T* − *S* 5. ((*S* ∩ *T*) ∪ *S*) 6. *U* − *S* (called the complement of *S*) 2. Given that the set *S* contains *n* elements, show that *S* has 2*n* subsets. 3. Let |*S*| stand for the number of elements in *S*. Show the validity of  4. Show that the following are equivalent. 1. *S* ⊂ *T* 2. *S* ∩ *T* = *S* 3. *S* ∪ *T* = *T* #### Section A.7 1. Determine the number of permutations of 10 objects taken six at a time. 2. Determine the number of combinations of 10 objects taken six at a time. That is, determine  3. Suppose there is a lottery in which four balls are drawn from an urn containing 10 balls. A winning ticket must show the balls in the order in which they are drawn. How many distinguishable tickets exist? 4. Suppose there is a lottery in which four balls are drawn from a bin containing 10 balls. A winning ticket must merely show the correct balls without regard for the order in which they are drawn. How many distinguishable tickets exist? 5. Use mathematical induction to prove the Binomial theorem, given in [Section A.7](LiB0099.html#1323). 6. Show the validity of the following identity.  7. Assume that we have *k*1 objects of the first kind, *k*2 objects of the second kind,…, and *km* objects of the *m*th kind, where *k*1 + *k*2 + … + *km* = *n*. Show that the number of distinguishable permutations of these *n* objects is equal to  8. Let *f*(*n, m*) be the number of ways to distribute *n* identical objects into *m* sets, where the ordering of the sets matters. For example, if *n* = 4, *m* = 2, and our set of objects is {*A, A, A, A*}, the possible distributions are as follows: 1. {*A, A, A, A*}, Ø 2. {*A, A, A*}, {*A*} 3. {*A, A*}, {*A, A*} 4. {*A*}, {*A, A, A*} 5. Ø, {*A, A, A, A*} We see that *f* (4, 2) = 5. Show that in general  Hint: Not that the set of all such distributions consists of all those that have *n A*'s in the first slot, all those that have *n* − 1 *A*'s in the first slot, …, and all those that have 0 *A*'s in the first slot. The use induction on *m*. 9. Show the validity of the following identity.  #### Section A.8 1. Suppose we have the lottery in Exercise 30. Assume all possible tickets are printed and all tickets are distinct. 1. Compute the probability of winning if one ticket is purchased. 2. Compute the probability of winning if seven tickets are purchased. 2. Suppose a poker hand (five cards) is dealt from an ordinary deck (52 cards). 1. Compute the probability of the hand containing four aces. 2. Compute the probability of the hand containing four of a kind. 3. Suppose a fair six-sided die (that is, the probability of each side turning up is ⅙) is to be rolled. The player will receive an amount of dollars equal to the number of dots that turn up, except when five or six dots turn up, in which case the player will lose $5 or $6, respectively. 1. Compute the expected value of the amount of money the player will win or lose. 2. If the game is repeated 100 times, compute the most money the player will lose, the most money the player will win, and the amount the player can expect to win or lose. 4. Assume we are searching for an element in a list of *n* distinct elements. What is the average (expected) number of comparisons required when the Sequential Search algorithm (linear search) is used? 5. What is the expected number of movements of elements in a delete operation on an array of *n* elements?