To find the finite summation of negative binomial.

Question

I'm looking to simplify the following expression. Basically need to remove the summation up to $t$

$$\sum_{k=j}^t \binom{k-1}{j-1} p^{k-j} q^j$$

where $p=1-q$, $t$ is a large finite number like $10^{15}$, $k\geq j$, $2\leq j\leq 50$.

Thanks

Answer 1

First we note: $$ {d^j \over dx^j}\frac{x^k}{1-x}=j!\sum_{i=0}^j\binom ki\frac{x^{k-i}}{(1-x)^{j-i+1}}.\tag1 $$

Then we have for $j\ge1$: $$\begin{align} \sum_{k=j}^n\binom{k-1}{j-1} p^{k-j}q^{j} &=\frac{q^j}{(j-1)!}\sum_{k=j}^n{d^{j-1} \over dp^{j-1}}p^{k-1}\\ &=\frac{q^j}{(j-1)!}{d^{j-1} \over dp^{j-1}}\sum_{k=j}^np^{k-1}\\ &=\frac{q^j}{(j-1)!}{d^{j-1} \over dp^{j-1}}\frac{p^{j-1}-p^{n}}{1-p}\\ &\stackrel{(1)}=q^j\sum_{i=0}^{j-1}\frac{\binom{j-1}ip^{j-1-i}-\binom{K}ip^{n-i}}{q^{j-i}}\\ &= p^{j-1}\sum_{i=0}^{j-1}\binom{j-1}i\left(\frac qp\right)^i -p^{n}\sum_{i=0}^{j-1}\binom{n}i\left(\frac qp\right)^i\\ &=1-\sum_{i=0}^{j-1}\binom{n}i p^{n-i}q^i.\tag2 \end{align}$$

Thus, to obtain the same result you can compute using (2) much shorter sum (according to $j\le50$).

---

A simple combinatorial proof of the identity: $$ \sum_{i=k}^{n}\binom{i-1}{k-1} p^{k}q^{i-k}=1-\sum_{i=0}^{k-1}\binom{n}{i}p^{i}q^{n-i} $$ can be found here.

---

Appendix. Proof of the equation (1) by induction.

Obviously the equation holds for $j=0$. Assume that it holds for some $j$. Then it holds for $j+1$ as well: $$\begin{align} {d^{j+1} \over dx^{j+1}}\frac{x^k}{1-x}&=\frac d{dx}\left[{d^{j} \over dx^{j}}\frac{x^k}{1-x}\right]\\ &\stackrel{I.H.}=\frac d{dx}\left[j!\sum_{i=0}^j\binom ki\frac{x^{k-i}}{(1-x)^{j-i+1}}\right]\\ &=j!\sum_{i=0}^j\binom ki \left[\frac{(k-i)x^{k-i-1}}{(1-x)^{j-i+1}} +\frac{(j-i+1)x^{k-i}}{(1-x)^{j-i+2}} \right]\\ &=j!\sum_{i=0}^j\left[\binom k{i+1}\frac{(i+1)x^{k-i-1}}{(1-x)^{j-i+1}} +\binom k{i}\frac{(j-i+1)x^{k-i}}{(1-x)^{j-i+2}} \right]\\ &=j!\left[\sum_{i=1}^{j+1}\binom k{i} \frac{i\,x^{k-i}}{(1-x)^{j-i+2}} +\sum_{i=0}^{j}\binom k{i}\frac{(j-i+1)x^{k-i}}{(1-x)^{j-i+2}} \right]\\ &=j!\left[\sum_{i=0}^{j+1}\binom k{i} \frac{i\,x^{k-i}}{(1-x)^{j-i+2}} +\sum_{i=0}^{j+1}\binom k{i}\frac{(j-i+1)x^{k-i}}{(1-x)^{j-i+2}} \right]\\ &=(j+1)! \sum_{i=0}^{j+1}\binom k{i}\frac{x^{k-i}}{(1-x)^{j-i+2}}. \end{align}$$

Answer 2

There's no closed form w.r.t. both $t$ and $j$, but for a fixed $j$, you can use $$\sum_{k=j}^{t}\binom{k-1}{j-1}x^{k-j}=\frac{1}{(j-1)!}\frac{d^{j-1}}{dx^{j-1}}\frac{1-x^t}{1-x},$$ giving a sum of only $\,\approx\!j$ terms after applying the product rule. Another approach is to consider the $t\to\infty$ asymptotics of your expression, assuming $q=q(t)$ is known.