Prove that $\sum_{k=1}^n\frac{\prod_{1\leq r\leq n, r\neq m}(x+k-r)}{\prod_{1\leq r\leq n, r\neq k}(k-r)}=1$

Question

For arbitrary $x$ and $1\leqslant m\leqslant n$, prove the following:

$$\sum_{k=1}^n\frac{\prod_{1\leq r\leq n, r\neq m}(x+k-r)}{\prod_{1\leq r\leq n, r\neq k}(k-r)}=1$$

I'm looking for a proof that does not involve the more general identity:

$$\sum_{k=1}^n\frac{\prod_{1\leqslant r\leqslant n-1}(y_k-z_r)}{\prod_{1\leqslant r\leqslant n, r\neq k}(y_k-y_r)}=1$$

I assume that the elementary proof I am looking for is based on getting the terms to their common denominator will somehow result in mass cancellation, but I am not really sure on how to get to it. Perhaps there is a less known formula. I don't really know because I didn't find too much books about the summation.

Note: The $m$ not being present anywhere except the condition of the product in the numerator is not a mistake. It intentionally excludes $m$-th term from each product in the numerator exactly to make things work.

Answer 1

Here is an elementary proof for the special case $m=1$.

The claim for the general case $1\leq m\leq n$ is: \begin{align*} \color{blue}{\frac{1}{n!}\sum_{k=1}^n\left(\prod_{{r=1}\atop{r\ne m}}^{n}(x+k-r)\right)\left(\prod_{{r=1}\atop{r\ne k}}^{n}(k-r)\right)^{-1}=1}\tag{1} \end{align*}

We write the denominator of (1) as \begin{align*} \left(\prod_{{r=1}\atop{r\ne k}}^{n}(k-r)\right)^{-1} &=\left(\prod_{r=1}^{k-1}(k-r)\prod_{r=k+1}^n(k-r)\right)^{-1}\\ &=\frac{1}{(k-1)!}\,\frac{(-1)^{n-k}}{(n-k)!}\\ &=\frac{(-1)^{n-k}k}{n!}\binom{n}{k}\tag{2} \end{align*}

and we can state the claim (1) equivalently for $1\leq m\leq n$ as: \begin{align*} \color{blue}{\sum_{k=1}^{n}\binom{n}{k}k(-1)^{n-k}\prod_{{r=1}\atop{r\ne m}}^{n}(x+k-r)=n!}\tag{3.1} \end{align*} and the special case $m=1$ as \begin{align*} \color{blue}{\sum_{k=1}^{n}\binom{n}{k}k(-1)^{n-k}(x+k)^{\underline{n-1}}=n!}\tag{3.2} \end{align*}

where we use the falling factorial notation $x^{\underline{n}}=x(x-1)\cdots(x-n+1)$. Since the claim (3.1) is independent of $x$ we consider in (3.2) a shifted variant: $x\to x+2$ to have a somewhat simpler starting point.

Denoting the left-hand side of (3.2) with $P_n(x)$ we obtain \begin{align*} \color{blue}{P_{n+1}(x)}&=\sum_{k=1}^{n+1}\binom{n+1}{k}k(-1)^{n+1-k}(x+k)^{\underline{n}}\\ &=\binom{n+1}{n+1}(n+1)(x+n+1)^{\underline{n}}\\ &\qquad-\sum_{k=1}^{n}\left(\binom{n}{k}+\binom{n}{k-1}\right)k(-1)^{n-k}(x+k)^{\underline{n}}\tag{4.1}\\ &=(n+1)(x+n+1)^{\underline{n}}-\sum_{k=1}^n\binom{n}{k}k(-1)^{n-k}(x+k)^{\underline{n}}\\ &\qquad+\sum_{k=0}^{n-1}\binom{n}{k}(k+1)(-1)^{n-k}(x+k+1)^{\underline{n}}\tag{4.2}\\ &=\sum_{k=0}^n\binom{n}{k}\left((k+1)(x+k+1)-k(x+k-n+1)\right)\\ &\qquad\quad\cdot(-1)^{n-k}(x+k)^{\underline{n-1}}\tag{4.3}\\ &=\sum_{k=0}^n\binom{n}{k}\left(k(n+1)+(x+1)\right)(-1)^{n-k}(x+k)^{\underline{n-1}}\tag{4.4}\\ &=(n+1)P_n(x)+(x+1)\underbrace{\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}(x+k)^{\underline{n-1}}}_{=0}\tag{4.5}\\ &\,\,\color{blue}{=(n+1)P_n(x)} \end{align*} Since $P_1(x)=1$ we obtain from (4.5) \begin{align*} \color{blue}{P_{n+1}(x)}=(n+1)P_n(x)=\cdots (n+1)!P_1(x)\color{blue}{=(n+1)!} \end{align*} and the claim (3.2) follows.

Comment:

• In (4.1) we separate the summand with $k=n+1$ and use the binomial identity $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$.

• In (4.2) we multiply out and shift the index of the right-hand sum by one to start with $k=0$.

• In (4.3) we collect equal terms and simplify in (4.4).

• In (4.5) we observe the left-hand sum is $(n+1)P_n(x)$ and the right-hand sum is $0$ which is shown for example in this post.

Answer 2

Following the work by @epi163sqrt we seek to prove the following identity where $1\le m\le n:$

$$\sum_{k=1}^n {n\choose k} k (-1)^{n-k} \prod_{r=1\atop r\ne m}^n (x+k-r) = n!.$$

The LHS is

$$\sum_{k=1}^n {n\choose k} k (-1)^{n-k} (x+k-1)^{\underline{m-1}} (x+k-1-m)^{\underline{n-m}}.$$

This is

$$\sum_{k=1}^n {n\choose k} k (-1)^{n-k} {x+k-1\choose m-1} (m-1)! {x+k-m-1\choose n-m} (n-m)!.$$

Hence an alternate form is

$$n \sum_{k=1}^n {n-1\choose k-1} (-1)^{n-k} {x+k-1\choose m-1} {x+k-m-1\choose n-m} = m {n\choose m}.$$

We will prove it for $x$ being an integer, equality for complex $x$ then follows by equality of polynomials. The LHS is

$$n [z^{m-1}] (1+z)^{x-1} [w^{n-m}] (1+w)^{x-m-1} \sum_{k=1}^n {n-1\choose k-1} (-1)^{n-k} (1+w)^k (1+z)^k \\ = n [z^{m-1}] (1+z)^x [w^{n-m}] (1+w)^{x-m} \sum_{k=1}^n {n-1\choose k-1} (-1)^{n-1-(k-1)} (1+w)^{k-1} (1+z)^{k-1}.$$

Working with the sum term, $$((1+w)(1+z)-1)^{n-1} = (w+z+wz)^{n-1} = (w+z(1+w))^{n-1},$$

restoring the extractors, $$n [z^{m-1}] (1+z)^x [w^{n-m}] (1+w)^{x-m} \sum_{q=0}^{n-1} {n-1\choose q} w^{n-1-q} z^q (1+w)^q.$$

Here we may lower the upper limit to $m-1$ owing to the coefficient extractor in $z:$

$$n \sum_{q=0}^{m-1} {n-1\choose q} {x-m+q\choose q+1-m} {x\choose m-1-q}.$$

Note very carefully that the middle binomial coefficient is zero when $q+1\lt m$. This is because the coefficient extractor in $w$ yields zero when $n-1-q\gt n-m$ or $m-1\gt q.$ This means that the only non-zero contribution to the sum originates with $q=m-1$ and we get

$$n {n-1\choose m-1} \times 1 \times 1 = m {n\choose m}$$ as claimed.