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 we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“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)