Prove series identity (Alternating reciprocal factorial sum)

[uart]

This alternating series indentity with ascending and descending reciprocal factorials has me stumped.
$$\frac{1}{k! \, n!} + \frac{-1}{(k+1)! \, (n-1)!} + \frac{1}{(k+2)! \, (n-2)!} \cdots \frac{(-1)^n}{(k+n)! \, (0)!} = \frac{1}{(k-1)! \, n! \, (k+n)}$$
Or more compactly,
$$\sum_{r=0}^{n} ( \frac{(-1)^r}{(k+r)! \, (n-r)!} ) = \frac{1}{(k-1)! \, n! \, (k+n)}$$

BTW. (Assume n,k integers, with $n \ge 0$ and $k \ge 1$.)

In this particular instance (for me), this series arises from a connection between the Gamma (Erlang) distribution and the Poisson distribution, where for certain parameters they represent the same probability scenario.
Specifically $1 - poisson\_cdf(k-1,\lambda) = gamma\_cdf(x,k,\lambda)$ at x=1. I know this is true, but if I try to prove it by doing a series expansion of each of those CDFs and equating coefficients, then I end up with the alternating series that has me stumped.

Has anyone seen that series before or know of any insights in how best to prove it?

 

[andrewkirk]

Identities of that kind often yield to induction. In this case you'd need two inductions, one on k and one on n.
I'd take the base case of k=1, n=0 and observe the identity's truth for that - both sides equalling 1.
Then I'd try proving that if the identity holds for k=k', n=n' then it holds for k=k',n=n'+1 and also for k=k'+1,n=n'. The result would follow by induction.

Sometimes the nature of the induction step proof requires us to have already proven more than one base case, eg not only k=1,n=0 but also k=1,n=1 and k=1,n=2. But if such a requirement exists it will become apparent when trying to prove one or other of the induction steps. In that case, you'd need to prove the additional base cases to complete the proof.

 

[anuttarasammyak]

Equation to be proved is transformed to
$$(-)^k\sum_{r=0}^n \ _{n+k}C_{r+k} (-)^{r+k}=\ _{n+k-1}C_n$$
Terms under summation are interpreted as coefficients of $x^{n-r}$ in expansion of $(x-1)^{n+k}$. I hope such a transformation could be helpful.

 

[uart]

Thanks all. Yes I did try induction first up, but I didn't get anywhere with it.

That's a great approach anuttarasammyak, looks very promising.

And using the combinations property that,
$$_nC_r = \, _{n-1}C_r + \, _{n-1}C_{r-1}$$
with the end condition that $_nC_0 = \, _{n-1}C_0$, I'm pretty sure I can make that whole LHS "telescope".

 

[uart]

Just sketching out a proof based on anuttarasammyak's insights.
$$\frac{1}{k! \, n!} + \frac{-1}{(k+1)! \, (n-1)!} + \frac{1}{(k+2)! \, (n-2)!} \cdots \frac{(-1)^n}{(k+n)! \, (0)!} = \frac{1}{(k-1)! \, n! \, (k+n)}$$
Multiplying both sides by $(k+n)!$ puts the proposed identity into the following form.
$$_{n+k}C_n -\, _{n+k}C_{n-1} +\, _{n+k}C_{n-2} - \cdots (-1)^n \,\, _{n+k}C_{n-n}= \, _{n+k-1}C_n$$
Using the relationship that, $\, _nC_k = \, _{n-1}C_k + \, _{n-1}C_{k-1}$ (for n,k >=1), the LSH can be written as,
$$[ _{n+k-1}C_n + \, _{n+k-1}C_{n-1}] - [ _{n+k-1}C_{n-1} + \, _{n+k-1}C_{n-2}] + \cdots (-1)^{n-1} [ _{n+k-1}C_1 + \, _{n+k-1}C_0] + (-1)^n [ _{n+k}C_0 ]$$
Here the second binomial coefficient in each square bracketed term cancels with the first binomial coeff in the following bracketed term, so the series telescopes leaving just the very first coeff of, $\, _{n+k-1}C_n$, hence LHS = RHS.