NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17479

Text File | 1992-12-29 | 5.5 KB | 122 lines

Newsgroups: sci.math
Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
From: [e-mail] (Vaughan R. Pratt)
Subject: Re: need proof:  (1 + 1/n)^n ==> e
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: Computer Science Department,  Stanford University.
References: <[e-mail]> <[e-mail]>
Date: Tue, 29 Dec 1992 09:48:42 GMT
Lines: 110

In article <[e-mail]> [e-mail] (Michael Somos) writes:
>The tone of the question suggests that a very elementary proof of
>the limit (1+1/n)^n is requested.  It is no trick to come up with
>fancy proofs that obscure rather than clarify.  An elementary proof
>may use a few more steps than a slick fancy proof but lead to more
>insight into the problem.  While the previously posted proofs all
>have some merit, so far no one has mentioned the following approach.
>
>[Very interesting method here]
>
>Note that this approach also defines the exponential function at the
>same time.  It uses nothing beyond the concept of limits and simple
>algebra.  It is truly elementary although it uses more steps.

One may show convergence of (1+1/n)^n by the following more mundane
means.  Let us denote by N those n that are powers of 2.

Proposition.  If 1 < M < N are powers of 2 then

    (1+1/M)^M < (1+1/N)^N < e < (1+1/N+1/N^2)^N < (1+1/M+1/M^2)^M

Proof.  1 + 1/M  <  1 + 2/(2M) + 1/(2M)^2  =  (1+1/(2M))^2.
Hence  (1 + 1/M)^M  <  ((1+1/(2M))^2)^M = (1+1/(2M))^(2M),
whence the first inequality follows by induction on powers of 2.

Also  1 + 1/M + 1/M^2  >  1 + 2/(2M) + 3/(2M)^2 + 2/(2M)^3 + 1/(2M)^4 for M>1
               =  (1 + 1/(2M) + 1/(2M)^2)^2.
Hence (1 + 1/M + 1/M^2)^M  >  (1 + 1/(2M) + 1/(2M)^2)^(2M), similarly
establishing the last inequality by induction on powers of 2.

Now the inequality (1+1/N)^N < (1+1/N+1/N^2)^N is immediate for all
N>0.  Thus the sequence (1+1/N)^N converges to some limit A from below,
while the sequence (1+1/N+1/N^2)^N converges to some limit B >= A from
above.  The pointwise ratio of these two sequences is
((1+1/N+1/N^2)/(1+1/N))^N = (1+1/(N(N+1))^N < (1+1/N^2)^N, whose N-th
power we have just shown to be bounded above by A (note that N^2 is a
power of 2 as required).  Hence the ratio is bounded above by A^{1/N}
and so tends to 1, whence A=B.  We may then define e to be that common
limit.  QED

(Although we have only shown convergence of that subsequence of
(1+1/n)^n for which n=N a power of 2, the convergence of the whole
sequence can be shown by extending the ratio argument to all n>0.)

-------------------------------

To atone for the mundaneness of this purely algebraic proof let me
describe how I obtained it.  I first proved the lower bound
geometrically, then stripped out the geometry, then obtained the upper
bound by analogy.  But first this.

           n
Define e  = (1+1/n) .   (So e  =  lim  e  ).
    n                        n->oo  n

Define D  as the difference operator
        n
               f(x + h) - f(x)
    (D f)(x)  =    -----------------    where h = 1/n.    (1)
      n               h

                          x      x
The neat thing is that D e   =  e  .             (2)
            n n      n

That is, (e_n)^x is a fixpoint of D_n.  This can be verified by
elementary algebra and without taking limits.  This is a little corner
of the beautiful calculus of finite differences, Boole's discrete
version of the infinitesimal calculus.
                   x
Now define the function Exp (x) = e  for x = 0, 1/n, 2/n, ..., 1, and
               n       n
extend it to the rest of the real interval [0,1] by linear
interpolation (connect the n+1 points with n line segments).  The
meaning of (2) with respect to this piecewise-linear curve is that the
slope of the line segment from Exp_n(m/n) to Exp_n((m+1)/n) is
Exp_n(m/n), for integer m in [0,n].

It can be shown with some effort that Exp_{n-1}(x) <= Exp_n(x) for all x in
[0,1].  (Outline: it suffices to show it for the vertices x = m/n of
Exp_n.  Letting p = n^2, Exp_{n-1}(m/n)/Exp_n(m/n) can be shown to be
(p^m - m p^{m-1})/(p-1)^m, equal to 1 for m=1 and less than 1 for m>1.)

What makes this argument a bit messy is that the vertices of Exp_n
don't line up neatly with those of Exp_{n-1}.  This can be fixed by
passing straight from Exp_n to Exp_2n, where Exp_n(m/n) <= Exp_2n(m/n)
can now be shown by the following simple geometric argument.  For each
segment of Exp_n there are two segments of Exp_2n.  Initially both f's
start at x=0 with f(x) = f'(x) = 1.  At x=1/2n, where f(x) = 1+1/2n for
both f's, the slope of Exp_2n increases to 1+1/2n causing it to rise
above Exp_n.  At x=1/n, Exp_n increases its slope to 1+1/n, but here
Exp_2n has reached (and therefore increases its slope to) (1+1/(2n))^2
= 1+1/n+1/(2n)^2 > 1+1/n.  Hence the slope of Exp_2n is at least that
of Exp_n everywhere (in contrast to the messy situation we encountered
with Exp_n vs. Exp_{n-1}), and strictly greater beyond x=1/2n.  In this
way Exp_2n makes a clean getaway from Exp_n, telling us that we can
expect a simpler argument if we focus on the subsequence of (1+1/n)^n
for which n is a power of 2.

This nice pictorial argument can now be boiled down to the purely
algebraic argument I gave at the beginning, at least for the part
showing that (1 + 1/M)^M  < (1+1/(2M))^(2M),

This doesn't explain where the upper bound of (1+1/N+1/N^2)^N comes
from.  That was just a lucky guess.

I'd be interested to know where these arguments can be found in the
literature.
--
Vaughan Pratt                There's safety in certain numbers.