Sum of terms in closed form

Question

I've reduced a problem that I'm doing to showing that for all $n \geq r$ natural numbers, $$\sum_{i=o}^{n-r}\frac{(-1)^i}{(r+i+1) \ i! \ (n-r-i)!} = \frac{r!}{(n+1)!}$$

Or equivalently writing $n = N +r$ that either $$\sum_{i=o}^{N}\frac{(-1)^i}{(r+i+1) \ i! \ (N-i)!} = \frac{r!}{(N+r+1)!}$$ or $$\frac{1}{N!}\sum_{i=o}^{N}\frac{(-1)^i}{(r+i+1)} {N \choose i} = \frac{r!}{(N+r+1)!}$$

I thought about trying induction, with the $n=r$ ie $N=0$ case being very easy, but it seems like the inductive step wouldn't work with the $(r+i+1)$ term not fitting well with the binomial coefficient or factorials... Any help is appreciated!

Answer 1

Let's define $f$ as $$f(x) := x^r\sum_{i=0}^N (-x)^i\binom{N}{i} = x^r(1-x)^N.$$

Moreover, we define $$F(x):= \int_0^x f(y)dy = x^{r+1}\sum_{i=0}^N \frac{(-x)^i}{r+i+1}\binom{N}{i} = \int_0^xy^r(1-y)^Ndy.$$

Using $x=1$, we just need to prove that $$\int_0^1y^r(1-y)^Ndy = \frac{N!r!}{(N+r+1)!}$$

We'll do this inducting on $N$ (for all $r$ at the same time). If $N=0$, this is trivial.

Now, $$\int_0^1y^r(1-y)^{N+1}dy = \Big[\frac{y^{r+1}}{r+1}\cdot(1-y)^{N+1}\Big]_0^1+\frac{N+1}{r+1}\cdot\int_0^1y^{r+1}(1-y)^Ndy = \frac{N+1}{r+1}\cdot \frac{N!(r+1)!}{(N+r+2)!} = \frac{(N+1)!r!}{(N+r+2)!}.$$

So, induction is completed.

Answer 2

We prove that

$$S_N = \sum_{q=0}^N \frac{(-1)^q}{q+r+1} {N\choose q} = \frac{1}{r+1} {N+r+1\choose N}^{-1}$$

by introducing

$$f(z) = (-1)^N N! \frac{1}{z+r+1} \prod_{p=0}^N \frac{1}{z-p}$$

which has the property that for $0\le q\le N$

$$\mathrm{Res}_{z=q} f(z) = (-1)^N N! \frac{1}{q+r+1} \prod_{p=0}^{q-1} \frac{1}{q-p} \prod_{p=q+1}^N \frac{1}{q-p} \\ = (-1)^N N! \frac{1}{q+r+1} \frac{1}{q!} \frac{(-1)^{N-q}}{(N-q)!} = \frac{(-1)^q}{q+r+1} {N\choose q}.$$

Now residues sum to zero and the residue of $f(z)$ at infinity is zero by inspection and we have

$$S_N = \sum_{q=0}^N \mathrm{Res}_{z=q} f(z) = - \mathrm{Res}_{z=-r-1} f(z) = - (-1)^N N! \prod_{p=0}^N \frac{1}{-r-1-p} \\ = N! \prod_{p=0}^N \frac{1}{r+1+p} = N! \frac{r!}{(N+r+1)!} = \frac{1}{r+1} {N+r+1\choose N}^{-1}.$$

This is the claim. Here we have supposed that $r$ is a non-negative integer. The closed form is valid for $r$ a complex number that is not a negative integer $-N-1\le r\le -1$, it does not simplify to factorials in the general case, however.