View Single Post
  #4  
Old 06-25-2005, 11:52 PM
BruceZ BruceZ is offline
Senior Member
 
Join Date: Sep 2002
Posts: 1,636
Default 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.
Reply With Quote