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!

  • 1
    $\begingroup$ You can get displayed equations by using double dollar signs instead of single dollar signs. They're centred, and things like fractions and sums with limits look less squashed and more readable. $\endgroup$ – joriki May 7 '13 at 8:12

First, we can reindex using $j=y-1$ to simplify:

$$ \sum_{j=k}^{n-1}\frac{\sum_{m=0}^{k-1}\binom{j-1}mj}{\sum_{m=0}^k\binom jm}\;. $$

For $n\gg k$, most terms have $j\gg k\ge m$, so we can approximate the sums by their largest terms and $\binom jm$ by $j^m/m!$, yielding

\begin{align} \sum_{j=k}^{n-1}\frac{j(j-1)^{k-1}/(k-1)!}{j^k/k!} &= k\sum_{j=k}^{n-1}\left(1-\frac1j\right)^{k-1} \\ &\approx k\int_k^{n-1}\left(1-\frac{k-1}x\right)\mathrm dx \\ &\approx kn-k(k-1)\log n \;. \end{align}

This is of course just a rough estimate without any error analysis.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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