What is the intermediate step in this negative binomial proof?

Question

On Slide 47 of these slides, there is a formula stating

$$ s_k(t) = - \sum_{j=0}^{k} s_j(0) \sum_{n=j}^{k} \frac{e^{-\lambda_n t} \prod_{m=j}^{k-1} \lambda_m }{\prod^{k}_{m=j, m \neq n} (\lambda_m - \lambda_n)} $$

I want to change it to the binomial form, and I see that the intermediate steps involve the application of the binomial theorem, I struggle to make it into a suitable form for that.

First step is the simplification with $ \lambda_k = k \lambda $ due to the problem set, so we obtain

$$ s_k(t) = - \sum_{j=0}^{k} s_j(0) \sum_{n=j}^{k} \frac{e^{- n \lambda t} \prod_{m=j}^{k-1} m }{\prod^{k}_{m=j, m \neq n} (m - n)} $$

What seems difficult is that we need to change the summation index, and even with writing out the terms I don't quite see what is going on.

I understand that the numerator can be factored out and the sign factored in.

$$ s_k(t) = \sum_{j=0}^{k} s_j(0) \prod_{m=j}^{k-1} m \sum_{n=j}^{k} \frac{- e^{- n \lambda t} }{\prod^{k}_{m=j, m \neq n} (m - n)} $$

where the product is

$$ \prod_{m=j}^{k-1} m = \frac{(k-1)!}{(j-1)!}$$

which needs an additional $ \ (k-j)! $ in its denominator to obtain the combination outside of the summation.

The exponential outside of the sum appears due to the shift of the summation.

$$ \sum_{n=j}^{k} e^{n \lambda t} = e^{-\lambda j t} \sum_{n=0}^{k-j} e^{-n \lambda t} $$ I would proceed showing

$$ \frac{1}{\prod^{k}_{m=j, m \neq n} (m - n)} = \frac{(j-n)!}{(k-n)!} $$

However, the term needed outside, does not appear so I would multiply the fraction with that

$$ \frac{1}{\prod^{k}_{m=j, m \neq n} (m - n)} = \frac{(k-j)!}{(k-j)!} \frac{(j-n)!}{(k-n)!} $$

which means we could borrow it for the outside term, and be left with after the change of summation $$ \frac{(k-j)! (j-n)!}{k-n!} \rightarrow \frac{(k-j)! (j-n-j)!}{k-n-j!} $$

where there is something wrong, because negative factorials are undefined.

Now I would evidently need to show that this is equal to

$$ {k-j \choose n } = \frac{(k-j)!}{n! (k-j-n)!} $$

Answer 1

Hint: The representation $$ \frac{1}{\prod^{k}_{m=j, m \neq n} (m - n)} = \frac{(j-n)!}{(k-n)!} $$ is not admissible, since $(j-n)!$ is as you already noted not defined for negative integral values ($j<n$). But, we can write \begin{align*} \frac{1}{\prod^{k}_{{m=j}\atop{m \neq n}} (m - n)} &=\frac{1}{\prod^{n-1}_{m=j} (m - n)}\cdot\frac{1}{\prod^{k}_{m=n+1} (m - n)}\\ &=\frac{(-1)^{n-j}}{(n-j)!}\cdot\frac{1}{(k-n)!}\tag{1} \end{align*}

Focussing on the inner sum of \begin{align*} s_k(t) = -\sum_{j=0}^{k} s_j(0) \sum_{n=j}^{k} \frac{e^{- n \lambda t} \prod_{m=j}^{k-1} m }{\prod^{k}_{m=j, m \neq n} (m - n)}\tag{2} \end{align*}

We obtain from (1) and (2) \begin{align*} \color{blue}{\sum_{n=j}^k}\color{blue}{\frac{e^{-n\lambda t}\prod_{m=j}^{k-1}m}{\prod_{{m=j}\atop{m\ne n}}^k(m-n)}} &=\sum_{n=j}^k\frac{e^{-n\lambda t}\frac{(k-1)!}{(j-1)!}}{\prod^{n-1}_{m=j} (m - n)\prod^{k}_{m=n+1} (m - n)}\\ &=\frac{(k-1)!}{(j-1)!}\sum_{n=j}^ke^{-n\lambda t}\frac{(-1)^{n-j}}{(n-j)!}\cdot\frac{1}{(k-n)!}\\ &=\frac{(k-1)!}{(j-1)!}\sum_{n=0}^{k-j}e^{-(n+j)\lambda t}\frac{(-1)^{n}}{n!}\cdot\frac{1}{(k-j-n)!}\tag{3}\\ &=\binom{k-1}{j-1}e^{-j\lambda t}\sum_{n=0}^{k-j}\binom{k-j}{n}\left(-e^{-\lambda t}\right)^n\\ &\,\,\color{blue}{=\binom{k-1}{j-1}e^{-j\lambda t}\left(1-e^{-\lambda t}\right)^{k-j}}\tag{4} \end{align*} resulting in \begin{align*} s_k(t)=-\sum_{j=0}^{k} s_j(0)\binom{k-1}{j-1}e^{-j\lambda t}\left(1-e^{-\lambda t}\right)^{k-j}\tag{5} \end{align*}

Comment:

• In (3) we shift the index to start with $j=0$.

• The minus sign in (2) is also part of (5) contrary to the stated formula in the paper. We check the equality of (2) and (5) for $k=1$: \begin{align*} \color{blue}{s_1(t)}&= -\sum_{j=0}^{1} s_j(0) \sum_{n=j}^{1} \frac{e^{- n \lambda t} \prod_{m=j}^{0} m }{\prod^{1}_{m=j, m \neq n} (m - n)}\\ &=-s_0(0)\sum_{n=0}^{1} \frac{e^{- n \lambda t} \prod_{m=0}^{0} m }{\prod^{1}_{m=0, m \neq n} (m - n)} -s_1(0)\sum_{n=1}^{1} \frac{e^{- n \lambda t} \prod_{m=1}^{0} m }{\prod^{1}_{m=1, m \neq n} (m - n)}\\ &=0-s_1(0)\frac{e^{-\lambda t}\cdot 1}{1}\\ &\,\,\color{blue}{=-s_1(0)e^{-\lambda t}}\\ \color{blue}{s_1(t)}&=-\sum_{j=0}^1 s_j(0)\binom{0}{j-1}e^{-j\lambda t}\left(1-e^{-\lambda t}\right)^{1-j}\\ &=-s_0(0)\cdot 0\cdot e^0\left(1-e^{-\lambda t}\right)-s_1(0)\binom{0}{0}e^{-\lambda t}\left(1-e^{-\lambda t}\right)^0\\ &\,\,\color{blue}{=-s_1(0)e^{-\lambda t}} \end{align*} affirming the validity of the minus sign.

Here we use the empty product $\prod_{m\in\emptyset}m=1$ and $\binom{p}{q}=0$ if $q<0$ (according for instance to (5.1) in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik).