Timeline for Sum of 'the first k' binomial coefficients for fixed $N$
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20, 2018 at 15:59 | comment | added | Martin Hairer | In the same vein, Cramér's theorem gives you upper and lower bounds of the type $\exp(-J(\alpha)N)$ with an explicit expression for $J$ when $k \approx \alpha N$ and $\alpha < 1/2$. Unless I messed up a quick calculation, one has $J(\alpha) = \alpha \log \alpha + (1-\alpha)\log(1-\alpha)$, but since $J(1/2) = -\log 2$ as expected, it's probably correct... | |
| Oct 1, 2017 at 10:10 | history | edited | Peter Heinig | CC BY-SA 3.0 |
I did nothing else than (0) inserting some 'paragraph-characters' while checking this answer, and (1), this being my reason for editing, replacing the accidental, inconsistent lower-case $n$ with the upper-case $N$ used in the OP and in the beginning of this answer.
|
| S Jan 1, 2017 at 16:59 | history | suggested | AvidLearner | CC BY-SA 3.0 |
corrected mistake in the sum, was really unclear
|
| Jan 1, 2017 at 16:03 | review | Suggested edits | |||
| S Jan 1, 2017 at 16:59 | |||||
| Nov 11, 2015 at 7:50 | history | edited | Alexey Ustinov | CC BY-SA 3.0 |
edited body
|
| Mar 27, 2010 at 17:04 | comment | added | Gerhard Paseman | When k is so close to N/2 that the above is not effective, one can then consider using 2^(N-1) - c (N choose N/2), where c = N/2 - k. Gerhard "Ask Me About System Design" Paseman, 2010.03.27 | |
| Mar 27, 2010 at 17:00 | comment | added | Gerhard Paseman | One can take this a step further. In addition to combining pairs of terms of the original sum N choose i to get a sum of terms of the form N+1 choose 2j+c, where c is always 0 or always 1, one can now take the top two or three or k terms, combine them, and use them as a base for a "psuedo-geometric" sequence with common ratio a square, cube, or kth power from the initial common ratio. This will give more accuracy at the cost of computing small sums of binomial coefficients. Gerhard "Ask Me About System Design" Paseman, 2010.03.27 | |
| Mar 6, 2010 at 8:03 | comment | added | Gerhard Paseman | Using the summation formula for Pascal's triamgle, you get a shorter geometric series approximation which may work well for k less than but not too close to N/2. This is (N+1) choose k + (N+1) choose (k-2) + ..., which has about half as many terms and ratio that is bounded from above by (k^2-k)/((N+1-k)(N+2-k)), giving [((N+1-k)(N+2-k))/((N+1-k)(N+2-k) -k^2 +k)]*[(N+1) choose k] as an uglier but hopefully tighter upper bound. Gerhard "Ask Me About System Design" Paseman, 2010.03.06 | |
| Mar 5, 2010 at 23:55 | vote | accept | mathy | ||
| Mar 5, 2010 at 22:35 | history | answered | Michael Lugo | CC BY-SA 2.5 |