Induction proof of $\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$

Question

Does anynone have some hints to prove the following equation by induction for all $n\geq 1$ and $m\in\mathbb{Z} $

$$\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$$

use for induction step:

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

Answer 1

Start with $$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (1+x)^{j} = (-x)^n $$

By applying binomial theorem to $(1 - (1+x))^n$.

Now multiply both sides with $(1+x)^{m+n-1}$ and differentiate ... times, and set $x$ to ..., and show by induction that ...

Answer 2

If you're looking for a proof by induction ... this isn't it. Notice

$$\sum_{j=0}^n (-1)^j{n \choose j} \left[\prod_{k=m+1}^{m+n-1}{(j+k)}\right]x^{j+m} =\sum_{j=0}^{n}(-1)^j{n\choose j}\frac{d^{n-1}}{dx^{n-1}}\left(x^{j+m+n-1}\right)$$

What can be done from here?

$$ \begin{array}{l} =\frac{d^{n-1}}{dx^{n-1}}\left[x^{m+n-1}\sum_{j=0}^n{n\choose j}(-x)^j\right] \\ =\frac{d^{n-1}}{dx^{n-1}} \left(x^{m+n-1}(1-x)^n\right) \\ =\sum_{l=0}^{n-1}\left(\frac{d^{n-1-l}}{dx^{n-1-l}}x^{m+n-1}\right)\left(\frac{d^{\,l}}{dx^l}(1-x)^n\right).\end{array}$$ Now, $\displaystyle\frac{d^{\,l}}{dx^l}(1-x)^n =(-1)^l \left[\prod_{r=n-l+1}^n r\right](1-x)^{n-l}$ and $(1-x)^{n-l}=0$ at $x=1$ when $l<n$.

Answer 3

We can write the product as a factorial times a binomial and then use Vandermonde's Identity to write that as a linear combination of $\binom{j}{i}$: $$ \begin{align} \prod_{k=m+1}^{m+n-1}(j+k) &=(n-1)!\binom{j+m+n-1}{n-1}\\ &=(n-1)!\sum_{i=0}^{n-1}\binom{j}{i}\binom{m+n-1}{n-i-1}\tag{1} \end{align} $$ $(1)$ is a degree $n-1$ polynomial in $j$, and in general, the $n^{\text{th}}$ forward difference of a polynomial of degree less than $n$ is $0$. In particular $$ \begin{align} &\sum_{j=0}^n(-1)^j\binom{n}{j}\prod_{k=m+1}^{m+n-1}(j+k)\\ &=(-1)^n\sum_{j=0}^n(-1)^{n-j}\binom{n}{j}\prod_{k=m+1}^{m+n-1}(j+k)\tag{2}\\ &=(-1)^n\sum_{j=0}^n(-1)^{n-j}\binom{n}{j}(n-1)!\sum_{i=0}^{n-1}\binom{j}{i}\binom{m+n-1}{n-i-1}\tag{3}\\ &=(-1)^n(n-1)!\sum_{i=0}^{n-1}\binom{m+n-1}{n-i-1}\sum_{j=0}^n(-1)^{n-j}\binom{n}{j}\binom{j}{i}\tag{4}\\ &=(-1)^n(n-1)!\sum_{i=0}^{n-1}\binom{m+n-1}{n-i-1}\sum_{j=0}^n(-1)^{n-j}\binom{n-i}{n-j}\binom{n}{i}\tag{5}\\ &=(-1)^n(n-1)!\sum_{i=0}^{n-1}\binom{m+n-1}{n-i-1}(1-1)^{n-i}\binom{n}{i}\tag{6}\\[12pt] &=0\tag{7} \end{align} $$ Explanation of Steps:

$(2)$: $(-1)^j=(-1)^n(-1)^{n-j}$

$(3)$: apply $(1)$

$(4)$: rearrange terms

$(5)$: $\displaystyle\binom{n}{j}\binom{j}{i}=\frac{n!}{(n-j)!\,i!\,(j-i)!}=\binom{n}{i}\binom{n-i}{n-j}$

$(6)$: $\displaystyle\sum_{j=0}^n(-1)^{n-j}\binom{n-i}{n-j}=(1-1)^{n-i}$

$(7)$: each term in $(6)$ is $0$ since $i\lt n$