# how to prove this sum/combinatorics identity

Prove

$$\frac{n!}{x(x+1)(x+2)...(x+n)} = \frac{(-1)^0 \cdot {n \choose 0}}{x} + \frac{(-1)^1 \cdot {n \choose 1}}{x+1} + \frac{(-1)^2 \cdot {n \choose 2}}{x+2} + ... + \frac{(-1)^n \cdot {n \choose n}}{x+n}$$

Prove true for n = 1,

$$\frac{1!}{x(x+1)} = \frac{1}{x} - \frac{1}{x+1} = \frac{1}{x(x+1)}$$

Assume true for n = k,

$$\frac{k!}{x(x+1)(x+2)...(x+k)} = \frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k \choose 2}}{x+2} + ... + \frac{(-1)^k \cdot {k \choose k}}{x+k} \hspace{3em} (1)$$

Prove true for n = k + 1,

$$\frac{(k+1)!}{x(x+1)(x+2)...(x+k+1)} = \frac{(-1)^0 \cdot {k+1 \choose 0}}{x} + \frac{(-1)^1 \cdot {k+1 \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k+1 \choose 2}}{x+2} + ... + \frac{(-1)^{k+1} \cdot {{k+1} \choose {k+1}}}{x+{(k+1)}} \hspace{3em} (2)$$

multiply both sides of $$(1)$$ by $$\frac{k+1}{x + (k+1)}:$$

$$\frac{k+1}{x + (k+1)} \cdot \frac{k!}{x(x+1)(x+2)...(x+k)} = \frac{k+1}{x + (k+1)} \cdot [ \frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k \choose 2}}{x+2} + ... + \frac{(-1)^k \cdot {k \choose k}}{x+k}]$$

$$\frac{(k+1)!}{x(x+1)(x+2)...(x+k+1)} = \frac{k+1}{x + (k+1)} \cdot [ \frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k \choose 2}}{x+2} + ... + \frac{(-1)^k \cdot {k \choose k}}{x+k}]$$

So LHS of $$(2)$$ is satifisfied:

LHS = $$\frac{k+1}{x + (k+1)} \cdot [ \frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k \choose 2}}{x+2} + ... + \frac{(-1)^k \cdot {k \choose k}}{x+k}]$$

= $$\frac{k+1}{x + (k+1)} \cdot [ \frac{{(-1)^0 \cdot {k \choose 0}}{} (x+1)(x+2)...(x+k) + {(-1)^1 \cdot {k \choose 1}}{} x(x+2)...(x+k) + {(-1)^2 \cdot {k \choose 2}}{} + ... + {(-1)^k \cdot {k \choose k}}{} x(x+1)(x+2)...(x+k-1)}{ x(x+1)(x+2)...(x+k)}]$$

= $$(k+1)[ \frac{{(-1)^0 \cdot {k \choose 0}}{} (x+1)(x+2)...(x+k+1) + {(-1)^1 \cdot {k \choose 1}}{} x(x+2)...(x+k+1 ) + {(-1)^2 \cdot {k \choose 2}}{} + ... + {(-1)^k \cdot {k \choose k}}{} x(x+1)(x+2)...(x+k)}{ x(x+1)(x+2)...(x+k+1)}]$$

= $$(k+1)[ \frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k \choose 2}}{x+2} + ... + \frac{(-1)^k \cdot {k \choose k}}{x+k+1}]$$

The problem might be in the last two lines somewhere, or perhaps it cannot be achieved in this direction of reasoning. Either way, if you have an idea on how to proceed with this line of thought, or another, i'm interested in seeing. Thanks.

EDIT: another attempt:

Since, $${n+1 \choose k} = {n \choose k} + {n \choose k -1}$$,

$$= \frac{(-1)^0 \cdot {k+1 \choose 0}}{x} + [ \frac{(-1)^1 \cdot {k+1 \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k+1 \choose 2}}{x+2} + ... + \frac{(-1)^k \cdot {k+1 \choose k}}{x+k} ]+ \frac{(-1)^{k+1} \cdot {{k+1} \choose {k+1}}}{x+{(k+1)}}$$ $$= \frac{(-1)^0 \cdot {k+1 \choose 0}}{x} + [\frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{2(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{2(-1)^2 \cdot {k \choose 2}}{x+2} + ... +\frac{2(-1)^k \cdot {k \choose k-1}}{x+k} + \frac{(-1)^k \cdot {k \choose k}}{x+k} ]+ \frac{(-1)^{k+1} \cdot {{k+1} \choose {k+1}}}{x+{(k+1)}}$$

$$= \frac{(-1)^0 \cdot {k+1 \choose 0}}{x} + 2[\frac{(-1)^0 \cdot {k \choose 0}}{x} + \frac{(-1)^1 \cdot {k \choose 1}}{x+1} + \frac{(-1)^2 \cdot {k \choose 2}}{x+2} + ... +\frac{(-1)^k \cdot {k \choose k}}{x+k} ]- \frac{(-1)^0 \cdot {k \choose 0}}{x} - \frac{(-1)^k \cdot {k \choose k}}{x+k} + \frac{(-1)^{k+1} \cdot {{k+1} \choose {k+1}}}{x+{(k+1)}}$$

$$= \frac{(-1)^0 \cdot {k+1 \choose 0}}{x} + 2[\frac{k!}{x(x+1)(x+2)...(x+k)}]- \frac{(-1)^0 \cdot {k \choose 0}}{x} - \frac{(-1)^k \cdot {k \choose k}}{x+k} + \frac{(-1)^{k+1} \cdot {{k+1} \choose {k+1}}}{x+{(k+1)}}$$

$$= 2[\frac{k!}{x(x+1)(x+2)...(x+k)}]- \frac{(-1)^k}{x+k} + \frac{(-1)^{k+1} \cdot {{k+1} \choose {k+1}}}{x+{(k+1)}}$$

$$= 2[\frac{k!}{x(x+1)(x+2)...(x+k)}]- (-1^k)[\frac{1}{x+k} - \frac{1}{x+{(k+1)}}]$$

$$= 2[\frac{k!}{x(x+1)(x+2)...(x+k)}]- (-1^k)[\frac{1}{(x+k)(x+k+1)} ]$$

Just after your (2), where you multiply both sides of (1) by $$\frac{k+1}{x+k+1}$$, you should multiply out the bracket term-by-term, using partial fractions, with the result $$\frac{k+1}{x+k+1}\cdot\frac{(-1)^r {k \choose r}}{x+r}=\frac{a}{x+r}+\frac{-a}{x+k+1},$$ where we require $$a(k+1-r)= (-1)^r (k+1){k \choose r},$$ so $$a= (-1)^r \frac{(k+1)k!}{(k+1-r)r!(k-r)!}=(-1)^r \frac{(k+1)!}{r!(k+1-r)!} =(-1)^r {k+1 \choose r}.$$ This gives the correct coefficient of each of the fractions in the $$n=k+1$$ result, except for the last: each multiplication contributes to this, so you end up with a coefficient of $$-\sum_{r=0}^k(-1)^r {k+1 \choose r}$$ which is $$(-1)^{k+1} {k+1 \choose k+1}$$ as required, since $$\sum_{r=0}^{k+1}(-1)^r {k+1 \choose r}=0$$.
• Thanks. I am having touble getting to $a = (-1)^r{k+1 \choose r}$, specifically $k+1$, I can verify the algebra for $k$ but then the coefficient is wrong...maybe there is an identity I am forgetting. Dec 4, 2022 at 9:41
Here is an answer using a different approach. We want to show for non-negative integer $$n$$ \begin{align*} \color{blue}{\frac{n!}{x(x+1)\cdots (x+n)}=\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{1}{x+k}}\tag{1} \end{align*} We consider the right-hand side of (1) and write it with common denominator. This gives \begin{align*} \sum_{k=0}^n(-1)^k\binom{n}{k}\frac{1}{x+k}=\frac{P(x)}{x(x+1)\cdots (x+n)}\tag{2} \end{align*} with $$P(x)$$ a polynomial in $$x$$ with degree $$\mathrm{deg} P(x)\leq n$$.
We take $$j, 0\leq j\leq n$$ and multiply (2) with $$(x+j)$$. We obtain \begin{align*} \sum_{{k=0}\atop{k\ne j}}^n(-1)^k\binom{n}{k}\frac{x+j}{x+k}+(-1)^j\binom{n}{j} &=\frac{(x+j)P(x)}{x(x+1)\cdots (x+n)}\tag{3} \end{align*} Evaluating (3) at $$x=-j$$ the sum at the left-hand side cancels, the factor $$(x+j)$$ at the right-hand side also and we obtain \begin{align*} (-1)^j\binom{n}{j}&=\frac{(x+j)P(x)}{x(x+1)\cdots (x+n)}\Big|_{x=-j}\\ &=\frac{P(-j)}{(-j)(-j+1)\cdots (-1)(1)(2)\cdots (n-j)}\\ &=(-1)^j\frac{P(-j)}{j!(n-j)!}\\ &=\frac{(-1)^n}{n!}P(-j)\binom{n}{j}\tag{4}\\ \end{align*} Simplifying (4) we get \begin{align*} \color{blue}{P(-j)-n!=0\qquad\qquad 0\leq j\leq n}\tag{5} \end{align*} We conclude from (5) since $$P(x)-n!$$ has $$n+1$$ zeros and degree less or equal $$n$$ we have \begin{align*} \color{blue}{P(x)-n!\equiv 0} \end{align*} and the claim (1) follows.