Re: Using probability to solve other types of problems
[ QUOTE ]
Here is one I just discovered. I claim that for all 0 < x < 1, and all integers n > 1,
(1 - x/n)^n > 1 - x
This could probably be proved for all values of n by induction, but then it would have to be proved for all x, perhaps by considering derivatives and logarithms.
[/ QUOTE ]
The usual algebraic proof is a very short one: Multiply out the left side.
1 - n * x/n + nC2 * x^2/n^2 - nC3 * x^3/n^3 ...
The first two terms simplify to 1-x. The third term is positive unless n=1. For all subsequent terms, x^k is less than x^(k-1), and nCk/n^k is less than half of nC(k-1)/n^(k-1), so each subsequent term is less than half the magnitude of the previous. So the series must converge, to something between 1-x and 1-x+x^2/2.
Of course this too has a probabilistic interpretation (each term is one more level of inclusion-exclusion, for sufficiently rare events successive levels of inclusion-exclusion contribute less and less to the final answer, and at most n levels are needed to obtain an exact probability.)
My favorite probability-inspired tricks are those that greatly simplify the evaluation of certain classes of integrals, by recognizing that the integrand is closely related to a PDF, i.e. a function that must integrate to 1.
(I always did think integrals were more fun than sums!)
|