the binomial coefficient ; Bertrand's proof shows that the number of favourable orders in which to count the votes is (though he does not give this number explicitly). And indeed after division this gives . Another equivalent problem is to calculate the number of random walks on the integers that consist of n steps of unit length, beginning at the origin and ending at the point m, that never become negative. Assuming n and m have the same parity and , this number is When and is even, this gives the Catalan number . [Note that if , then must be even. Otherwise, the random walk cannot end at . This can be seen as follows: let be the number of "positive" moves, i.e., to the right, and let be the number of "negative" moves, i.e., to the left. Since and , we have and . Since and are integers, if , then must be an integer. In other words, must be even.] Proof by reflection For A to be strictly ahead of B throughout the counting of the votes, there can be no ties. Separate the counting sequences according to the first vote. Any sequence that begins with a vote for B must reach a tie at some point, because A eventually wins. For any sequence that begins with A and reaches a tie, reflect the votes up to the point of the first tie (so any A becomes a B, and vice versa) to obtain a sequence that begins with B. Hence every sequence that begins with A and reaches a tie is in one-to-one correspondence with a sequence that begins with B, and the probability that a sequence begins with B is , so the probability that A always leads the vote is the probability of sequences that tie at some point the probability of sequences that tie at some point and begin with A or B the probability of sequences that tie at some point and begin with B the probability that a sequence begins with B Proof by induction Another method of proof is by mathematical induction: We loosen the condition to . Clearly, the theorem is correct when , since in this case the first candidate will not be strictly ahead after all the votes have been counted (so the probability is 0). Clearly the theorem is true if p > 0 and q