Homework answers / question archive / (a) In an election, there are two candidates, A and B; the number of votes cast is 2n

(a) In an election, there are two candidates, A and B; the number of votes cast is 2n

Sociology

Share With

(a) In an election, there are two candidates, A and B; the number of votes cast is 2n. Each candidate receives exactly n votes; but, at every intermediate point during the count, A has received more votes than B. Show that the number of ways this can happen is the Catalan number Cn. (Hint: A leads by just one vote after the first vote is counted. Suppose that this next occurs after 21 + 1 votes have been counted. Then there are f(i) choices for the count between these points, and f(n-i) choices for the rest of the count, where f(n) is the required number; so we obtain the Catalan recurrence.] HARDER PROBLEM. Can you construct a bijection between the bracketed expressions and the voting patterns in (a)? (b) In the above election, assume only that, at any intermediate stage, A has received at least as many votes as B. Prove that the number of possibilities is now Cn+1. (Hint: Give A an extra vote at the beginning of the count, and B an extra vote at the end.) 16. A clown stands on the edge of a swimming pool, holding a bag containing n red and n blue balls. He draws the balls out one at a time and discards them. If he draws a blue ball, he takes one step back; if a red ball, one step forward. (All steps have the same size.) Show that the probability that the clown remains dry is 11. 1 n 2. Prove the following identities: (a) FR - Fn+1Fn-1 = (-1)" for n > 1. (b) Fi = Fn+2 – 1. (c) F-1 + f2 = Fan, Fr-1Fn + FnFn+1 = Fan+1. In/2] (d) Fn = i=0 2 (47) i=0 3. Show that Fn is composite for all odd n > 3. Hey all, want to make some clarifications on HW5: 9(a)(ii). You are to find the general solution, but it is not necessary that you find the roots to the characteristic polynomial explicitly (you can use symbols to represent the roots or give approximate values). You should justify why the general solution formula you are using works (think about how roots play a role in this). 15. The author has a mistake (it should say 2n+2 votes cast). Possible vote casting: 2 votes cast: AB 4 votes cast: AABB 6 votes cast: AAABBB, AABABB 8 votes cast: AAAABBBB, AAABABBB, AAABBABB, AABAABBB, AABABABB (A must always be strictly in the lead with votes, until the very end, so ABAB doesn't work because at the second step they would be tied: "at every intermediate point during the count, A has received more votes than B.') 1-1 9. (a) Solve the following recurrence relations. (i) f(n + 1) = f(n)?, f(0) = 2. (ü) f(n + 1) = f(n) + f(n − 1) + f(n − 2), f(0) = f(1) = f(2) = 1. (iii) f(n + 1) =1+ f(i), f(0) = 1. (b) Show that the number of ways of writing n as a sum of positive integers, where the order of the summands is significant, is 2n-1 for n > 1. i=0 mith n On a sheet of paper, please complete the following questions from your textbook. Then, scan and upload your work. Exercises 2a (Hint: Prove by induction.), 9 (ii), 15(a)(You don't need to solve the additional harder problem) in 4.8.