What is the result of the following binomial sum?

Question

When computing the expectation of $S_n^{-1}I_{[S_n > 0]}$ with $S_n \sim \text{binomial}(n, p)$, I need to evaluate the sum:

\begin{align*} \sum_{k = 1}^n \frac{1}{k}\binom{n}{k}p^{k}(1 - p)^{n - k} \end{align*} for $p \in (0, 1)$.

Is there any well-known binomial identity that can be directly applied to get the above sum? Or any other methods?

My attempt:

Denote $\sum_{k = 1}^{n - 1} \frac{1}{k}\binom{n}{k}p^{k}(1 - p)^{n - k}$ by $f(p), p \in (0, 1)$. Differentiating once with respect to $p$, we get \begin{align*} f'(p) = - \frac{n}{1 - p}f(p) + \frac{1}{p(1 - p)}(1 - p^n - (1 - p)^n) \end{align*}

This nonhomogeneous linear ODE seems solvable but could be tedious...

Answer 1

Here is a transformation which simplifies the sum somewhat by extracting Harmonic numbers $H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}$.

We obtain for $n\geq 1$ \begin{align*} \color{blue}{f_n}&\color{blue}{=\sum_{k = 1}^n \frac{1}{k}\binom{n}{k}p^{k}(1 - p)^{n - k}}\\ &=\sum_{k = 1}^n \frac{1}{k}\left(\binom{n-1}{k}+\binom{n-1}{k-1}\right)p^{k}(1 - p)^{n - k}\\ &=\sum_{k = 1}^n \frac{1}{k}\binom{n-1}{k}p^{k}(1 - p)^{n - k} +\frac{1}{n}\sum_{k = 1}^n \binom{n}{k}p^{k}(1 - p)^{n - k}\\ &=(1-p)f_{n-1}+\frac{1}{n}\left((p+(1-p))^n-(1-p)^n\right)\\ &\color{blue}{=(1-p)f_{n-1}+\frac{1}{n}-(1-p)^n\frac{1}{n}}\\ \end{align*}

Iterating this recurrence relation we get with $f_1=p$

\begin{align*} \color{blue}{f_n}&=(1-p)f_{n-1}+\frac{1}{n}-(1-p)^n\frac{1}{n}\\ &=(1-p)^2f_{n-2}+(1-p)\frac{1}{n-1}+\frac{1}{n}-(1-p)^n\left(\frac{1}{n-1}+\frac{1}{n}\right)\\ &=(1-p)^3f_{n-3}+(1-p)^2\frac{1}{n-2}+(1-p)\frac{1}{n-1}+\frac{1}{n}\\ &\qquad-(1-p)^n\left(\frac{1}{n-2}+\frac{1}{n-1}+\frac{1}{n}\right)\\ &=\cdots\\ &=(1-p)^{n-1}f_1+\sum_{k=0}^{n-2}(1-p)^k\frac{1}{n-k}-(1-p)^n\left(H_n-1\right)\\ &=(1-p)^{n}\left(\frac{p}{1-p}+1-H_n\right)+\sum_{k=0}^{n-2}(1-p)^{n-k-2}\frac{1}{k+2}\tag{1}\\ &\color{blue}{=(1-p)^{n}\left(-H_n+\sum_{k=1}^{n}(1-p)^{-k}\frac{1}{k}\right)}\tag{2}\\ \end{align*}

Comment:

• In (1) we change the order of summation $k\rightarrow n-2-k$, use $f_1=p$ and do some simplifications.

• In (2) we do some simplifications, shift the index and start with $k=1$.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\left.\sum_{k = 1}^{n}{1 \over k}{n \choose k}p^{k}\pars{1 - p}^{n - k} \,\right\vert_{\ p\ \in\ \pars{0,1}} = \pars{1 - p}^{n}\sum_{k = 1}^{n}{n \choose k}\pars{p \over 1 - p}^{k} \int_{0}^{1}t^{k - 1}\,\dd t \\[5mm] = &\ \pars{1 - p}^{n}\int_{0}^{1} \sum_{k = 1}^{n}{n \choose k}\pars{pt \over 1 - p}^{k}\,{\dd t \over t} = \pars{1 - p}^{n}\int_{0}^{1} \bracks{\pars{1 + {pt \over 1 - p}}^{n} - 1}\,{\dd t \over t} \\[5mm] = &\ \pars{1 - p}^{n}\int_{0}^{p/\pars{1-p}} {\pars{1 + t}^{n} - 1 \over t}\,\dd t = \bbx{% np\,\pars{1 - p}^{n - 1}\ {}_{3}\mrm{F}_{2}\pars{2,1,1,-n;2,2;{p \over p - 1}}} \end{align}

$\ds{{}_{p}\mrm{F}_{q}}$ is a Generalized Hypergeometric Function.