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