Re: Using probability to solve other types of problems
[ QUOTE ]
[ 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.
[/ QUOTE ]
I was being overly dramatic for effect. [img]/images/graemlins/smile.gif[/img] Here's an even shorter proof. Take the derivative of the left side:
-(1 - x/n)^(n-1) > -1. Since the slope of 1 - x = -1, and since the expressions are equal for x = 0, the left side must always be greater than 1 - x.
The probability proof is only long with the detailed explanation. It's really almost a one-liner. The important thing is that we can "discover" this algebraic truth from only probability considerations.
|