# Summing ratio of ratio of partial sums of binomial coefficients

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!

-
Your formula would look a little nicer if you let the index $y$ start at $k$ instead of $k+1$ -- i.e., $$\sum_{y = k}^n \frac{\sum_{m = 0}^{k - 1} {y - 1 \choose m}y}{\sum_{m = 0}^k {y \choose m}}.$$ (Technically the outer sum should now stop at $n-1$, but I think it looks nicer with an $n$.) – Barry Cipra May 7 '13 at 17:24
If I haven't made too many mistakes, the numerator in my previous comment can be rewritten as $\sum_{m=1}^k m{y \choose m}$ which, to my eye at least, makes thing look yet nicer. Whether it helps obtain a useful approximation, I can't say. – Barry Cipra May 7 '13 at 17:33
I really prefer my suggestion in the other post where the partial sum is written as s and is understood to depend on y and k. Rewriting ((y-1) choose k)/s as t, one gets the summand as y/(2+t), where t ranges from near 1/2^k to near (y-k)/k, giving that the sum will be something like n(k - O(log k)). Gerhard "Ask Me About System Design" Paseman, 2013.05.07 – Gerhard Paseman May 7 '13 at 19:08
I now see better what you're saying Gerhard. Trying to give the idea more thought now...And thank you both for the comments. – ELW May 7 '13 at 19:33
Let $T$ be $\sum_{m = 0}^{k - 1} y {y - 1 \choose m}$ and let $S$ be $\sum_{m = 0}^k {y \choose m}$. First $$T = \sum_{m = 0}^k m {y \choose m}$$ then also $$T = \sum_{m = 0}^{k - 1} (y - 1 - m) {y \choose m} \\\\= - (T - k {y \choose k}) + (y - 1) \sum_{m = 0}^{k - 1} {y \choose m} \\\\= - T + (y - 1) S - (y - 1 - k) {y \choose k}.$$ Consequently $$\frac{T}{S} = 0.5((y - 1) - \frac{(y - 1 - k) {y \choose k}}{S}).$$ The comments really simplify the equation. However because of the S in the numerator, I still can't approximate the formula. Any other advice? Thanks! – ELW May 8 '13 at 2:25

$$\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.