# Infinite Sum with Combinatoric Expression

Calculate the value of the infinite sum, where $0<p<1$ and $r,n\in\mathbb{Z}_{\ge1}$:

$$\sum_{y=1}^\infty \binom{r+y-1}{y}y^n(1-p)^y$$

Just for context, this is the $n^{th}$ moment of the zero-truncated negative binomial distribution (with a few constant terms removed for simplicity).

Don't even know where to get started with this one.

## 3 Answers

Don't know if this really helps, but this is a starting point (I may have made some mistakes, please carefully check the last formula, if you have computed it for small values use it). Let $F(X)=\frac{1}{1-X}=\sum_{k=0}^{\infty}X^k$. We denote $D$ the operator on power series of derivation by $X$ and $XD$ the operator of derivation and multiplication by $X$. Then :

$$D^{r-1}F(X)=\sum_{k=0}^{\infty}(r-1)!\binom{k}{r-1}X^{k-r+1} =\sum_{k=0}^{\infty}(r-1)!\binom{k+r-1}{r-1}X^k$$

Finally :

$$(XD)^nD^{r-1}F(X)=\sum_{k=0}^{\infty}(r-1)!\binom{k+r-1}{r-1}k^nX^k$$

Ok so now $G_{n,r}(X):=(XD)^nD^{r-1}F(X)$ is a regular rational fraction which you can compute (by tedious computations that are easily handled by a computer). The convergence radius of $G_{n,r}$ is clearly $1$, thus we can evaluate $G_{n,r}$ in $1-p$ which gives us the sum you want up to $(r-1)!$

For instance :

$$G_{1,1}(X)=\frac{X}{(1-X)^2}\text{ thus the number you are looking for is } \frac{1-p}{p^2}$$

$$G_{2,1}(X)=\frac{X}{(1-X)^2}+\frac{2X}{(1-X)^3}\text{ thus...}$$

$$G_{3,1}(X)=\frac{X}{(1-X)^2}+\frac{6X}{(1-X)^3}+\frac{6X^3}{(1-X)^4}\text{ thus...}$$

To have a finite sum formula out of this, I suggest you use the following two results :

1. $D^{r-1}F(X)=(r-1)!\frac{1}{(1-X)^r}$ (easy)

2. if you are given a power series $f(X)$ and you want to know $(XD)^nf(X)$ there is a nice formula for $n\geq 1$

$$(XD)^nf(X)=\sum_{\ell=1}^ns(\ell,n)X^{\ell}D^{\ell}f(X)$$ where $s(k,n)$ are Stierling numbers of the second kind (it is not hard to prove: induction). So that :

$$G_{n,r}(X)=\sum_{\ell=1}^ns(\ell,n)X^{\ell}D^{\ell+r-1}f(X)$$ $$G_{n,r}(X)=\sum_{\ell=1}^ns(\ell,n)X^{\ell}\frac{(\ell+r-1)!}{(1-X)^{\ell+r}}$$

So that the number you are looking for is :

$$\sum_{\ell=1}^ns(\ell,n)\frac{(\ell+r-1)!(1-p)^{\ell}}{(r-1)!p^{\ell+r}}$$

\newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}} \begin{align} \sum_{k=1}^\infty\binom{r+k-1}{k}\,k^n\,(1-p)^k &=\sum_{k=1}^\infty\binom{-r}{k}\sum_{j=0}^n\stirtwo{n}{j}\binom{k}{j}\,j!\,(p-1)^k\tag1\\ &=\sum_{j=0}^n\sum_{k=1}^\infty\binom{-r}{j}\stirtwo{n}{j}\binom{-r-j}{k-j}\,j!\,(p-1)^k\tag2\\ &=\sum_{j=0}^n\binom{-r}{j}\stirtwo{n}{j}\,j!\,(p-1)^jp^{-r-j}\tag3\\ &=\sum_{j=0}^n\binom{r+j-1}{j}\stirtwo{n}{j}\,j!\,(1-p)^jp^{-r-j}\tag4 \end{align} where $\stirtwo{n}{j}$ is a Stirling Number of the Second Kind. Note that $(4)$ is a finite sum.

Explanation:
$(1)$: $\binom{r+k-1}{k}=(-1)^k\binom{-r}{k}$ and $k^n=\sum\limits_{j=0}^n\stirtwo{n}{j}\binom{k}{j}\,j!$
$(2)$: $\binom{-r}{k}\binom{k}{j}=\binom{-r}{j}\binom{-r-j}{k-j}$
$(3)$: $\sum\limits_{k=1}^\infty\binom{-r-j}{k-j}(p-1)^k=(p-1)^jp^{-r-j}$
$(4)$: $\binom{-r}{j}=(-1)^j\binom{r+j-1}{j}$

• I've added explanation for each step. It would be nice to understand the explanation for the downvote. – robjohn Feb 11 '18 at 15:08
• This one must be very useful $k^n=\sum\limits_{j=0}^n\stirtwo{n}{j}\binom{k}{j}\,j!$ (in general, I mean) – Yuriy S Feb 12 '18 at 1:09

While Clément Guérin and robjohn gave excellent answers, and as a finite sum no less, I think it might be useful to provide the hypergeometric form for this series.

Changing the index by $1$, and introducing a new variable $q=1-p$, we can write the series as:

$$q \sum_{k=0}^\infty \binom{k+r}{k+1} (k+1)^n q^k=\frac{q}{\Gamma(r)} \sum_{k=0}^\infty \frac{\Gamma(k+r+1)}{(k+1)!} (k+1)^n q^k=$$

$$=\frac{q}{\Gamma(r)} \sum_{k=0}^\infty \frac{\Gamma(k+r+1)}{k!} (k+1)^{n-1} q^k$$

The $0$th term is:

$$T_0=rq$$

The ratio of successive general terms is:

$$\frac{T_{k+1}}{T_k}=\frac{(k+r+1)(k+2)^{n-1}}{(k+1)^n}q =\frac{(k+r+1)(k+2)^{n-1}}{(k+1)^{n-1}} \frac{q}{k+1}$$

Which makes the sum:

$$q \sum_{k=0}^\infty \binom{k+r}{k+1} (k+1)^n q^k=r~q~{_{n} F_{n-1}}\left(r+1,2,\ldots,2;1, \ldots,1;q \right)$$

Where ${_{n} F_{n-1}}$ is a generalized hypergeometric function.

Or, getting back to the original paramter:

$$\sum_{j=1}^\infty \binom{r+j-1}{j}j^n(1-p)^j=r~(1-p)~{_{n} F_{n-1}}\left(r+1,2,\ldots,2;1, \ldots,1;1-p \right)$$

Not much useful for computations directly, but various hypergeometric identities can usually be used to simplify the result (in this case to Clément Guérin and robjohn's finite sums with Stirling numbers).

As a curiosity:

$${_{n} F_{n-1}}\left(2,\ldots,2;1, \ldots,1;1-p \right)=\frac{1}{p^{n+1}} \sum_{j=0}^{n-1} A(n,j) (1-p)^j$$

Where $A(n,j)$ are Eulerian numbers.