8
$\begingroup$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial sums such as (for $ m < n $)

$\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}.$

If $0 the second case can be approximated with the normal distribution using the central limit theorem. If anyone could suggest some general approach to solving problems like these I'd be very grateful.

  • 1
    Just as a note, they're kinda the same problem;$\sum_{k=0}^m{n\choose k}x^k(1-x)^{n-k}=(1-x)^n\sum_{k=0}^n{n\choose k}\left(\frac{x}{1-x}\right)^k;$ $y=\frac{x}{1-x}\iff x=\frac{y}{1+y}.$2011-11-22

1 Answers 1

6

As pointed out in the comments, if you can solve one problem you can solve the other, so I'm just going to give a bound for the first sum. Also, $x > 0$. (It seems like the case $x<0$ might be trickier.) We have

$\begin{align} &\frac{\binom{n}{m}x^m + \binom{n}{m-1}x^{m-1} + \cdots + \binom{n}{0}x^0}{\binom{n}{m}x^m} \\ &= 1 + \frac{m}{(n-m+1)x} + \frac{m(m-1)}{(n-m+1)(n-m+2)x^2} + \cdots + \frac{m!}{n^{\underline{m}}!x^m} \\ &\leq 1 + \frac{m}{(n-m+1)x} + \left(\frac{m}{(n-m+1)x}\right)^2 + \cdots + \left(\frac{m}{(n-m+1)x}\right)^m, \end{align}$

which is the partial sum of a geometric series. Therefore,

$\sum_{k=0}^m \binom{n}{k} x^k \leq \binom{n}{m} x^m \frac{1 - r^{m+1}}{1-r},$ where $r = \frac{m}{(n-m+1)x}.$

Of course, if $r < 1$, then we obtain the simpler expression $\sum_{k=0}^m \binom{n}{k} x^k \leq \binom{n}{m} x^{m+1} \frac{n-m+1}{(n-m+1)x-m}.$

(To give credit where credit is due, this is an adaption of Michael Lugo's answer to a related question on Math Overflow.)

  • 0
    thanks, Mike. Is there any way to estimate the size of error? $O(\frac{1}{m})$ maybe?2011-12-07