5
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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$.) $\endgroup$ May 7, 2013 at 17:24
  • $\begingroup$ 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. $\endgroup$ May 7, 2013 at 17:33
  • $\begingroup$ 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 $\endgroup$ May 7, 2013 at 19:08
  • $\begingroup$ I now see better what you're saying Gerhard. Trying to give the idea more thought now...And thank you both for the comments. $\endgroup$
    – ELW
    May 7, 2013 at 19:33
  • $\begingroup$ 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! $\endgroup$
    – ELW
    May 8, 2013 at 2:25

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for tying the equations out. Now things are much more clear! $\endgroup$
    – ELW
    May 8, 2013 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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