Proof By Induction
Another method of proof is by mathematical induction:
- Clearly the theorem is true if p > 0 and q = 0 when the probability is 1, given that the first candidate receives all the votes; it is also true when p = q > 0 since the probability is 0, given that the first candidate will not be strictly ahead after all the votes have been counted.
- Assume it is true both when p = a − 1 and q = b, and when p = a and q = b−1, with a > b > 0. Then considering the case with p = a and q = b, the last vote counted is either for the first candidate with probability a/(a + b), or for the second with probability b/(a + b). So the probability of the first being ahead throughout the count to the penultimate vote counted (and also after the final vote) is:
- And so it is true for all p and q with p > q > 0.
Read more about this topic: Bertrand's Ballot Theorem
Famous quotes containing the words proof and/or induction:
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)
“They relieve and recommend each other, and the sanity of society is a balance of a thousand insanities. She punishes abstractionists, and will only forgive an induction which is rare and casual.”
—Ralph Waldo Emerson (1803–1882)