$\sum_{i=1}^n\frac{1}{i}\binom{n}{i}p^i(1-p)^{n-i}\leq\frac{K}{n} $

Question

How can it be proved that, if $0<p<1$, then $$\sum_{i=1}^n\frac{1}{i}\binom{n}{i}p^i(1-p)^{n-i}\leq\frac{K}{n} $$ for some constant $K$? Thanks in advance for every suggestion.

Answer 1

Here is an alternative way to Jack's method, which perhaps might be slightly more general when dealing with binomial sums.

Recall that by the binomial theorem we have that $$\sum_{i=0}^{n}{n\choose i}p^{i}x^{i}(1-p)^{n-i}= (px+1-p)^{n}$$

Now integrating both sides over the interval $[0,1]$ we get $$\sum_{i=0}^{n}\frac{1}{i+1}{n\choose i}p^{i}(1-p)^{n-i}= \frac{1-(1-p)^{n+1}}{p(n+1)}$$

Possibly omitting the non-negative term $(1-p)^{n}$ and invoking the trivial estimates $\frac{1}{2i}\leq \frac{1}{i+1}$ and $\frac{1}{n+1}<\frac{1}{n}$, we finally arrive at $$\sum_{i=1}^{n}\frac{1}{i}{n \choose i}p^{i}(1-p)^{n-i} \leq \frac{1}{n}\cdot \frac{2-2(1-p)^{n+1}}{p}\leq \frac{2}{n\cdot p}$$

Answer 2

We have:

$$\begin{eqnarray*} S(p,n)=\sum_{i=1}^n \binom{n}{i}\frac{p^i(1-p)^{n-i}}{i} &=& (1-p)^n \frac{}{}\sum_{i=1}^{n}\binom{n}{i}\left(\frac{p}{1-p}\right)^i\frac{1}{i}\\&=&(1-p)^n \int_{0}^{\frac{p}{1-p}}\sum_{i=1}^{n}\binom{n}{i}x^{i-1}\,dx\\&=&(1-p)^n \int_{0}^{\frac{p}{1-p}}\frac{(x+1)^n-1}{x}\,dx\\&=&(1-p)^n \int_{0}^{\frac{p}{1-p}}\frac{(\frac{1}{1-p}-x)^n-1}{\frac{p}{1-p}-x}\,dx\\&=&\int_{0}^{1}\frac{(1-py)^n-(1-p)^n}{1-y}\,dy\end{eqnarray*}$$ so it is enough to estimate the last integrand function with something like $e^{-k y}$ (Laplace method) to prove our claim. Assuming $p>\frac{1}{2}$ and $np>1$ it happens that: $$ \frac{(1-py)^n-(1-p)^n}{1-y}\leq \exp\left((1-np)y\right) $$ so we have:

$$ S(n,p) \leq \int_{0}^{+\infty} e^{(np-1)y}\,dy = \frac{1}{np-1}. $$