MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
Thank you for tying the equations out. Now things are much more clear! – ELW May 8 '13 at 7:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.