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