Euler Series Transformation
---------------------------
Lemma 1:

For all non-negative integer k:

     oo
    --- C(n,k)
    >   ------- = 1
    --- 2^{n+1}
    n=k

Proof:

Multiply the sum by x^k and sum

     oo  oo
    --- --- C(n,k)
    >   >   ------- x^k
    --- --- 2^{n+1}
    k=0 n=k

       oo  n
      --- --- C(n,k)
    = >   >   ------- x^k
      --- --- 2^{n+1}
      n=0 k=0

       oo
      --- (x+1)^n
    = >   -------
      --- 2^{n+1}
      n=0

      1     1
    = - ---------
      2 1-(x+1)/2

       1
    = ---
      1-x

       oo
      ---
    = >   x^k
      ---
      k=0

Equating the coefficients of x proves the lemma.

QED

Lemma 2:

For any non-negative integer N,

     N   N
    --- ---  -n-1                          -N-1
    >   >   2     (C(n,k)-C(n,k+1)) = 1 - 2
    --- ---
    k=0 n=k

Furthermore, for any non-negative integers, k and N,

     N
    ---  -n-1
    >   2     (C(n,k)-C(n,k+1)) >= 0
    ---
    n=k

Proof:

     N   N
    --- ---  -n-1
    >   >   2     (C(n,k)-C(n,k+1))
    --- ---
    k=0 n=k

       N   n
      --- ---  -n-1
    = >   >   2     (C(n,k)-C(n,k+1))
      --- ---
      n=0 k=0

       N
      ---  -n-1    n     n
    = >   2     ( 2 - ( 2 - 1 ) )
      ---
      n=0

           -N-1
    = 1 - 2

Lemma 1 implies that

     oo
    ---  -n-1
    >   2     (C(n,k)-C(n,k+1)) = 1 - 1 = 0                  [1]
    ---
    n=k

Note that

               n-k
    C(n,k+1) = --- C(n,k)
               k+1

Therefore, under the conditions above that 0 <= k <= n, the terms in [1]
are positive when n < 2k+1 and then negative when n > 2k+1.  Since the
sum in [1] is 0, all of its partial sums must be positive.

QED

Corollary 2.1:

     N     N
    --- | ---  -n-1                   |        -N-1
    >   | >   2     (C(n,k)-C(n,k+1)) | = 1 - 2
    --- | ---                         |
    k=0   n=k

Proof:

Since the partial sum inside the absolute value is always positive,
this is the same sum as in Lemma 2.

QED

Theorem (Euler Series Transformation):

If

     oo
    ---
    >   a
    ---  k
    k=0

converges, then

     oo        n               oo
    ---  -n-1 ---             ---
    >   2     >   C(n,k) a  = >   a
    ---       ---         k   ---  k
    n=0       k=0             k=0

Proof (Euler Series Transformation):

Formally, we would simply like to use Lemma 1 after switching the order
of summation.  However, the sum of a_k may not converge absolutely, so
we must switch the order of summation with care.

Let S_k be the partial sum

          k
         ---
    S  = >   a
     k   ---  j
         j=0

and S be the limit of S_k as k->oo.

Then, a_k = S_k - S_{k-1}.  This yields the partial sum

     N         n
    ---  -n-1 ---
    >   2     >   C(n,k) a
    ---       ---         k
    n=0       k=0

       N         n
      ---  -n-1 ---
    = >   2     >   C(n,k) ( S - S   )
      ---       ---           k   k-1
      n=0       k=0

       N         n
      ---  -n-1 ---
    = >   2     >   (C(n,k)-C(n,k+1)) S
      ---       ---                    k
      n=0       k=0

       N   N
      --- ---  -n-1
    = >   >   2     (C(n,k)-C(n,k+1)) S                      [2]
      --- ---                          k
      k=0 n=k

Pick an e > 0.  Choose an M so that |S_k - S| < e for all k >= M
and so that 2^{-M-1} < e.  Lemma 1 implies that for each non-positive
integer k,

     oo
    ---  -n-1
    >   2     (C(n,k)-C(n,k+1)) = 1 - 1 = 0
    ---
    n=k

Choose an N >= M so that for all m >= N and k < M,

       m
    | ---  -n-1                   |   e
    | >   2     (C(n,k)-C(n,k+1)) | < -                      [3]
    | ---                         |   M
      n=k

Now we have from [2],

         N         n
    |   ---  -n-1 ---                |
    | ( >   2     >   C(n,k) a ) - S |
    |   ---       ---         k      |
        n=0       k=0

           N   N
      |   --- ---  -n-1                           |
    = | ( >   >   2     (C(n,k)-C(n,k+1)) S ) - S |  
      |   --- ---                          k      |
          k=0 n=k

           N   N
      |   --- ---  -n-1                                  -N-1  |
    = | ( >   >   2     (C(n,k)-C(n,k+1)) ( S - S ) ) - 2    S |
      |   --- ---                            k                 |
          k=0 n=k

           M-1  N
       |   --- ---  -n-1                               |
    <= | ( >   >   2     (C(n,k)-C(n,k+1)) ( S - S ) ) |
       |   --- ---                            k        |
           k=0 n=k

            N   N
       |   --- ---  -n-1                               |
     + | ( >   >   2     (C(n,k)-C(n,k+1)) ( S - S ) ) |
       |   --- ---                                k    |
           k=M n=k

        -N-1
     + 2     |S|

       e
    <= - M max(|S - S|)          (choice of N)
       M         k

     + e                         (Corollary 2.1 and choice of M)


     + e |S|                     (choice of M)


    = e (max(|S - S|) + 1 + |S|)                             [4]
               k

Thus,

     oo        n                   oo
    ---  -n-1 ---                 ---
    >   2     >   C(n,k) a  = S = >   a
    ---       ---         k       ---  k
    n=0       k=0                 k=0

QED

An identity that sometimes proves useful when using the Euler Series
Transformation is

     n                     n
    ---     k C(n,k)      ---  1
    >   (-1)  ------ = n! | | ---
    ---         k+x       k=0 k+x
    k=0

Rob Johnson