Partial sum of binomial

Question

I 'm trying to figure out a closed form solution for the following summation:

$\sum_{j=0}^{\omega} j{n \choose j}p^{j}(1-p)^{n-j}$ where $\omega < n$

Is there any closed form solution?

Answer 1

As I pointed out in a comment, 'closed expression' is a somewhat vague definition, but expressions that involve hypergeometric functions/Jacobi/Legendre polynomials are generally speaking not closed.

For your specific problem, this is called a partial sum of rows of Pascal's triangle, and it doesn't exist in 'closed form' in the sense the full sum of rows does (i.e. $\sum_{k=0}^{n}\binom{n}{k} = 2^n$).

What you can do here is express is find upper and lower bounds on it. If $$ S_n (r) = \sum_{k=0}^{r} \binom{n}{k} a^k = 1 +\binom{n}{1} a + \cdots \binom{n}{r}a^r $$ which you'll get by doing some simple algebra with the original expression and obtaining some constant, you can divide through the last term and get $$ \frac{S_n(r)}{\binom{n}{r}a^r} = \frac{1}{\binom{n}{r}a^r} + \frac{\binom{n}{1} a}{\binom{n}{r}a^r}+ \cdots 1 $$ Now simplify every term that involves the ratio of binomial coefficients, and then use Stirling's formula for each remaining term keeping in mind that for each $\varepsilon>0$ $$ \frac{1}{1+ \varepsilon} \bigg(\frac{n}{e} \bigg)^n \sqrt{2 \pi n} <n!< (1+ \varepsilon)\bigg(\frac{n}{e} \bigg)^n \sqrt{2 \pi n} $$ If you get stuck you can look up a 1994 article by T. Worsch called 'Lower and upper bounds for sums of binomial coefficients).

Answer 2

The ordinary generating function with the indexing variable $x^{i}$ is: $$x\cdot n\cdot p\cdot\frac{\left(x\cdot p+\left(1-p\right)\right)^{n-1}}{1-x}$$ Demonstration:

First we write out the source generating function with parameters: $y$ to get the $j$ factor and indexing variable $x$; and then apply the standard OGF partial sum operator $\frac{1}{1-x}$.
$\mathcal{G=}\left(x\cdot p\cdot y+\left(1-p\right)\right)^{n}$

$\frac{\partial\mathcal{G}}{\partial y}=x\cdot n\cdot p\cdot\left(x\cdot p\cdot y+\left(1-p\right)\right)^{n-1} $
Set $y=1$ and apply $\frac{1}{1-x}$

For $\mathcal{G}_{s}=x\cdot n\cdot p\cdot\frac{\left(x\cdot p+\left(1-p\right)\right)^{n-1}}{1-x}$

---

To get partial sums to $\omega$

$\frac{1}{\omega!}\frac{\partial^{\omega}\mathcal{G}_{s}}{\partial x^{\omega}}|_{x=0}$