I would like to approximate the following when $n \gg k$.


$\sum\_{y = k + 1}^n \frac{\sum\_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum\_{m = 0}^k {y - 1 \choose m}}.$


The formula can be re-written as


$\sum\_{y = k + 1}^n \frac{(y - 1) + \sum\_{m = 1}^{k - 1} {y - 1 \choose m + 1} (m + 1)}{\sum\_{m = 0}^k {y - 1 \choose m}}.$


However since the partial sum of binomial coefficient does not closed form, I could not see any way to further simplify the formula. Any help is much appreciated. Thanks!



Summing ratio of ratio of partial sums of binomial coefficients
$$ \sum\_{m=0}^k \binom{z+1}{m} = \sum\_{m=0}^k [ \binom{z}{m-1} + \binom{z}{m} ]
= \binom{z}{k} + 2 \sum\_{m=0}^{k-1}\binom{z}{m},$$ when $z \geq k$. So the sum
can be rewritten as


$$ \sum\_{z=k}^{n-1} \frac{z}{2 + \binom{z-1}{k}/\sum\_{m=0}^{k-1}\binom{z-1}{m}}. $$ Let's
call this summand $a\_z$ . Note that $a\_k = k/2, a\_{k+1} = (k+1)/(2+1/(2^k - 1))$, and for small
values of $j$, $a\_{k+j} = (k+j)/(2 + \binom{k+j-1}{j-1}/(2^{k+j-1}-\sum\_{m=0}^{j-1} \binom{k+j-1}{m}))$
. Now as z increases, the denominator of $a\_z$ eventually tends monotonically to $(z+k)/k$, which means
$a\_z$ tends to $k$ from below. Thus the entire sum has an upper bound (for $n \gg k$) of $(n-k)k$.
Further, for sufficiently large integers $l$, $a\_{lk}$ is slightly larger than $lk/(l+1)$, so I imagine the actual sum differs from the upper bound by
a $O(n\log{k}) $ amount.


Gerhard "Ask Me About System Design" Paseman, 2013.05.08


