Timeline for Lower bound for sum of binomial coefficients?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17, 2011 at 19:13 | comment | added | user13006 | Thanks again. You're right of course. This turned out to be much easier than I anticipated. I think I was so excited to see the latex typeset in real-time that I followed up too soon. I do need the case where the terms are relevant, so I'm happy to know how to do that now. | |
| Feb 16, 2011 at 17:33 | comment | added | Emil Jeřábek | I should probably also point out that the extra terms are relevant only when $k$ is close to $n/2$. If $k\le\alpha n$ for some constant $\alpha<1/2$, then it all boils down to $\sum_{i\le k}\binom ni=\Theta\left(\binom nk\right)$, as Anthony Quas wrote in his answer. | |
| Feb 16, 2011 at 17:28 | comment | added | Emil Jeřábek | I just simplified the expression since there are constant factors missed anyway. Taking $x=k/(n-k+1)$ gives $1-x=(n-2k+1)/(n-k+1)$. However, $n-k+1=\Theta(n)$ by the assumptions, hence $(n-2k+1)/(n-k+1)=\Theta((n-2k)/n)=\Theta(1-2k/n)$. Also, note that this argument gives an upper bound on the sum. The matching lower bound is slightly more complicated to prove, you basically need to show that $(k-i)/(n-k+i+1)$ is not too smaller than $k/(n-k+1)$ for sufficiently many $i$'s so that it works out. | |
| Feb 16, 2011 at 16:54 | comment | added | user13006 | So, more detail: geometric series comes from $${n \choose k-1}/{n \choose k} = \frac{k}{n-k+1} > \frac{k-i}{n-k+i+1}$$ Let $x = \frac{k}{n-k+1}$. Then $x \leq \frac{2k}{n}$, and $x > \frac{k-i}{n-k+i+1}$ for $k \geq i > 0$, so geometric series gives lower bound. $$\sum_{i=0}^{k} {n \choose i} \leq {n \choose k} \sum_{j = 0}^{k} x^j \leq {n \choose k}/(1-x)$$ matches your statement for $x = \frac{2k}{n}$. But I believe you must have intended to use $x = \frac{k}{n-k}$ or $\frac{k}{n-k+1}$, since otherwise it is not tight. Setting $\epsilon = 1/2$ in your 2nd version gives correct version. | |
| Feb 16, 2011 at 16:51 | comment | added | user13006 | You're right. I spoke too soon after waking up. The problem is that the $f(x) = x^{1/x}$ term is immediately multiplied by an $f(\frac{x}{x-1})$ term, and while a single $f(x)f(x/(x-1))$ term is maximized for $x=2$, optimizing sums over this product is not as clear. And if you can't precisely estimate the base of an exponential term, you're in trouble. Your approach is better -- and simple too! In retrospect it's the obvious thing to do. So I see it's covered by Proposition A.4 in your paper, with some slightly different notation. | |
| Feb 16, 2011 at 16:37 | vote | accept | user13006 | ||
| Feb 16, 2011 at 13:37 | history | answered | Emil Jeřábek | CC BY-SA 2.5 |