In an election, candidate A receives n votes and candidate B receives m votes, where n > m. Assuming that all of the (n*m)! n!m! orderings of the votes are equally likely, let

Pn,m

denotes the probability that A is always ahead in the counting of the votes.

(a) Compute P2,1, P3,1, P3,2, P4,1, P4,2, P4,3.

(b) Find Pn,1, Pn,2.

(c) (b) Find Pn,1,Pn,2. (c) On the basis of your results in parts (a) and (b), conjecture the value of

Pn,m

(d) (d) Derive a recursion for

Pn,m

in terms of

Pn-1,m

and

Pn,m-1

by conditioning on who receives the last vote. (e) Use part (d) to verify your conjecture in part (c) by an induction proof on n+m.