HW 9 Answer Key

Section 4.6

10.a. C(6 + 12 − 1, 12) = C(17, 12) = 6188 b. C(6 + 36 − 1, 36) = C(41, 36) = 749398 c. C(6 + 12 − 1, 12) = C(17, 12) = 6188 If we first pick out the two of each kind, then we have picked 2 · 6 = 12 croissants. We had NO choice . This leaves only one dozen to pick without restriction. d. We first compute then number of ways to violate the restriction. By choosing at least three broccoli croissants. This can be done in C(6 + 21 − 1, 21) = C(26, 21) = 65780 ways, since once we have picekd the three broccoli croisstants there are 21 left to pick with ‘out restriction. Since there are C(6 + 24 − 1, 24) = C(29, 24) = 118755 ways to pick 24 croissants without any restriction, there must by 118755 − 65780 = 52975 ways to choose two dozen croissants with no more than two broccoli. e. Eight croissants are specified, so this problem is the same as chooisng 24-8=16 croissants without restriction, which can be done in C(6 + 16 − 1, 16) = C(21, 16) = 20349 ways. f. First let us include all the lower bound restrictions. If we choose the required 9 croissants, then there are 24 − 9 = 15 left to choose, and if there were no restriction on the broccoli croissants then there would be C(6 + 15 − 1, 15) = C(20, 15) = 15504 ways to make the selections. If in addition we were to violate the broccoli restriction by chooisng at least four broccoli croissants, there would be C(6+11−1, 11) = C(16, 11) = 4368 choices. Therefore the number of ways to make the selection without violating the restriction is 15504 − 4368 = 11136.

12. There are 5 things to choose from, repetitions allowed, and we want to choose 20 things, order not important. Therefore by theorem 2 the answer is C(5 + 20 − 1, 20) = C(24, 20) = C(24, 4) = 10, 626.

16. a.We require each x_{i} ≥ 2.This uses up 12 of the 29 total required. The number of solutions is therefore C(6 + 29 − 12 − 1, 29 − 12) = C(22, 17) = 26, 334. b.The restrictions use up 22 of the total, leaving a free total of 7. Therefore the answer is C(6+7−1, 7) = C(12, 7) = 792. c. The no. of solutions without restrictions is C(6 + 29 − 1, 29) = C(34, 29) = 278256. The no. of solutions violating the restriction by having x_{1} ≥ 6 is C(6 + 23 − 1, 23) = C(28, 23) = 98280. Therefore the answer is 278256 − 98280 = 179, 976. d. The no. of solutions with x_{2} ≥ 9 (as required) but without the restriction on x_{1} is C(6 + 20 − 1, 20) = C(25, 20) = 53130. The no. of solution violating the additional restriction by having x_{1} ≥ 8 is C(6 + 12 − 1, 12) = C(17, 12) = 6188. Therefore the answer is 53130 − 6188 = 46, 942.

18.\frac{20!}{2!4!3!1!2!3!2!3!} or about 5.9 x 10^{13}.

26. \frac{11!}{4!4!2!}

32. We simply need to choose the 6 positions, out of the 14 available, to make 1’s. There are C(14, 6) = 3003 ways to do this.

36.We can describe any travel in a unique way by a sequence of 4 x’s, 3 y’s, 5 z’s and 4 w’s. By theorem 3: \frac{16!}{4!3!5!4!} = 50, 450, 400 sequences.

38. From theorem 4, the answer is \frac{52!}{13!^{a}} ≈ 5.4 ∗ 10^{2}8, since each player gets 13 cards.

42.There are 5 bars (chosen books), and therefore there are 6 places where the 7 stars (nonchosen books) can fit. Each of the second through fifth of these slots must have at least 1 star in it, so that adjacent books are not chosen. Once we have placed these 4 stars, there are 3 stars left to be placed in the 6 slots. The number of ways to do this is therefore C(6 + 3 − 1, 3) = C(8, 3) = 56

SECTION 5.1

2a. −3a_{n−1} + 4_{n−2} = −3 · 0 + 4 · 0 = a_{n} b. −3a_{n−1} + 4_{n−2} = −3 · 1 + 4 · 1 = a_{n} c. −3a_{n−1} + 4_{n−2} = −3 · (−4)^{n−1} + 4 · (−4)^{n−1} = (−4)^{n−2}((−3)(−4) + 4) = (−4)^{n−2} · 16 = (−4)^{n−2}(−4)^{2} = (−4)^{n} = a_{n} d. −3a_{n−1} + 4_{n−2} = −3 · (2 · (−4)^{n−1} + 3)+ 4 · (2(−4)^{n−1} + 3) = (−4)^{n−2}((−6)(−4) + 4 · 2) − 9 + 12 = (−4)^{n−2} · 32 = (−4)^{n−2}(−4)^{2} · 2 + 3 = 2 · (−4)^{n} + 3 = a_{n}

4. c.One possible answer is a_{n} = a_{n−1} + 2 e.Since a_{n} − a_{n−1} = n^{2} − n − 1^{2} = 2n − 1, we have a_{n} = a_{n−1} + 2n − 1. f. a_{n} = a_{n−1} + 2n h. a_{n} = na_{n−1}.

8. Let a_{n} be the population in billions, n years after 1988.

a. a_{n} = 1.03a_{n−1}, with a_{0} = 6. b.a_{n} = 6(1.03)^{n} c. a_{1}3 = 6(1.03)^{1}3 ≈ 8.8 billion people.

14. The recurrence relation is a_{n} = a_{n−1} + a_{n−2} + 2a_{n−5} + 2a_{n−10} + a_{n−20} + a_{n−50} + a_{n−100}. There would be a 100 initial conditions.

18 a. Let a_{n} be the nubmer of bit strings of length n containing three consecutive 0’s. In order to construct a bit string of length n containinig three consecutive 0’s we would start with 1 and follow with a string of length n − 1 containing three consecutive 0’s, or we could start with a 01 and follow with a string of length n − 2 containing three consecutive 0’s, or we could start with a 001 and follow with a string of lenght n − 3 containing three consecutive 0’s, or we could start with a 00 and follow with any string of lenght n − 3. These four cases are mutually exclusive and exhaust the possibilities for how the string might start. From this analysis we can immediately write down the recurrence relation, valid for all n ≥ 3: a_{n} = a_{n−1} + a_{n−1} + a_{n−3} + 2^{n−3}. b. There are no bit strings of length 0, 1, or 2 containing three consecutive 0’s, so the initial conditions are a_{0} = a_{1} = a_{2} = 0 c. We will compute a_{3} through a_{7} using the recurrence relation: a_{3} = a_{2} + a_{1} + a_{0} + 2^{0} = 0 + 0 + 0 + 1 = 1 a_{4} = a_{3} + a_{2} + a_{1} + 2^{1} = 1 + 0 + 0 + 2 = 3 a_{5} = a_{4} + a_{3} + a_{2} + 2^{2} = 3 + 1 + 0 + 4 = 8 a_{6} = a_{5} + a_{4} + a_{3} + 2^{3} = 8 + 3 + 1 + 8 = 20 a_{7} = a_{6} + a_{5} + a_{4} + 2^{4} = 20 + 8 + 3 + 16 = 47 There are 47 bit strings of length 7 containing three consecutive 0’s.

22.a. Let a_{n} be the no. of ways to climb n stairs.In order to climb n stairs, a person must either start with a step of one stair and then climb n − 1 stairs (in a_{n−1} ways) or else start with a step of 2 stairs and then climb n − 2 stairs(in a_{n−2} ways), or start with a step of 3 stairs and then climb n − 3 stairs(in a_{n−3}) ways. Thus the recurrence relation is : a_{n} = a_{n−1} + a_{n−2} + a_{n−3}, for n ≥ 3 . b. The initial conditions are a_{0} = 1, a_{1} = 1, anda_{2} = 1, since there is 1 way to climb no stairs(do nothing), only one way to climb 1 stair, two ways to climb 2 stairs( 1 step twice, or two steps at once). c. Each term a_{n} is the sum of 3 previous terms. Therefore a_{1} = 1, a_{2} = 2, a_{3} = 4, a_{4} = 7, a_{5} = 13, a_{6} = 24, a_{7} = 44, a_{8} = 81.Thus answer is 81 ways.

29.a.a_{n} = a_{n−1} + a_{n−2} for n ≥ 2. b.a_{0} = 1, a_{1} = 1 c. 89.

32. a.R_{1} is very clearly 2, R_{2} = 4, R_{3} = 8. Let us analyze what happens when the n^{th} great circle is added. It must intersect each of the other circles twice(at diametrically opposite points), and each of these results in 1 prior region being split into 2. There are n − 1 previous great circles, and therefore 2(n − 1) new regions. Therefore R_{n} = R_{n−1} + 2(n − 1). b.R_{n} = 2(n − 1) + R_{n−1} = 2(n − 1) + 2(n − 2) + R_{(}n − 2) = 2(n − 1) + 2(n − 2) + 2(n − 3) + R_{n−3} · · · = n(n − 1) + 2 = n^{2} − n + 2 .

36. Let a_{n} be the no. of coverings.

a. If the right-most domino is positioned vertically, then we have a covering of the left-most n−1 columns which can be done in a_{n−1} ways. If the right-most domino is placed horizontally, then there must be anather domino directly beneath it, and these together cover the last two columns. The first n − 2 columns can be covered in a_{n−2} ways. Thus we obtain the recurence a_{n} = a_{n} − 1 + a_{n} − 2. b. a_{1} = 1, a_{2} = 2. c. The sequence obtained is the Fibonacci sequence, shifted by one. The sequence is 1, 2, 3, 5, 8, 13, 21, 534, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...., so the answer is 2584.

38. The initial conditions are of course true. We prove the reccurence relation by induction on n, starting with base case n = 5, and n = 6, in which cases we find 5f_{1} + 3f_{0} = 5 = f_{5}and5f_{2} + 3f_{1} = 8 = f_{6}. assume the inductive hypothesis. Then we have 5f_{n−4} +3f_{n−5} = 5(fn − 5+f_{n−6})+3(f_{n−6} +f_{n−7}) = (5f_{n−5} +3f_{n−6})+(5f_{n−6} +3f_{n−7}) = f_{n−1} + f_{n−2} = f_{n} (using both inductive hypothesis and recursive definition of fibonacci numbers). We prove f_{5n} is divisible by 5 by induction on n. It is true for n = 1 as f_{5} = 5 is divisible by 5. Let it be true for f_{5n}. Then f_{5(n+1)} = f_{5n+5} = 5f_{5n+1} + 3f_{5n} is divisible by 5 as both summands are divisible by 5.