TAOCP 1.2.3 Exercise 34

Exercise 34. [M25] Prove that

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

provided that $1 \le m \le n$ and $x$ is arbitrary. For example, if $n = 4$ and $m = 2$, then

$$\frac{x(x-2)(x-3)}{(-1)(-2)(-3)} + \frac{(x+1)(x-1)(x-2)}{(1)(-1)(-2)} + \frac{(x+2)x(x-1)}{(2)(1)(-1)} + \frac{(x+3)(x+1)x}{(3)(2)(1)} = 1.$$

Verified: no
Solve time: 3m14s

Let

$$ f(x)=\sum_{k=1}^n \frac{\displaystyle\prod_{\substack{1\le r\le n\ r\ne m}}(x+k-r)} {\displaystyle\prod_{\substack{1\le r\le n\ r\ne k}}(k-r)}. $$

For each $k$, the numerator is a polynomial in $x$ of degree $n-1$, while the denominator is independent of $x$. Hence $f(x)$ is a polynomial of degree at most $n-1$.

We will prove that

$$ f(1-j)=1 \qquad (j=1,2,\dots,n). $$

Since these are $n$ distinct values of $x$, it will follow that the polynomial $f(x)-1$, whose degree is at most $n-1$, has $n$ roots. Therefore $f(x)\equiv1$.

Fix $j\in{1,\dots,n}$. Substituting $x=1-j$ gives

$$ f(1-j)= \sum_{k=1}^n \frac{\displaystyle\prod_{\substack{1\le r\le n\ r\ne m}}(1-j+k-r)} {\displaystyle\prod_{\substack{1\le r\le n\ r\ne k}}(k-r)}. $$

Consider the $k$-th summand. The factor $1-j+k-r$ vanishes when

$$ r=k+1-j. $$

We first determine when this value of $r$ actually appears among the indices of the numerator product.

Since $1\le k\le n$ and $1\le j\le n$,

$$ 1\le k+1-j\le n $$

holds exactly when $k\ge j$. Thus, for every $k\ge j$, the numerator contains the factor corresponding to $r=k+1-j$.

Now suppose $k\ne j+m-1$. Then

$$ k+1-j\ne m, $$

so the index $r=k+1-j$ is not omitted from the numerator product. Therefore the numerator contains the zero factor

$$ 1-j+k-(k+1-j)=0, $$

and hence the whole $k$-th term vanishes.

Thus the only possible nonzero term occurs when

$$ k=j+m-1. $$

If this value of $k$ does not lie in ${1,\dots,n}$, then every term vanishes and we would obtain $f(1-j)=0$, contradicting the identity we seek. Therefore we must examine more carefully which $k$ actually contribute.

Observe that if $k<j$, then

$$ k+1-j\le0, $$

so there is no index $r\in{1,\dots,n}$ making a factor vanish. But if $k<j$, then

$$ k\le j-1, $$

and therefore

$$ k-m\le j-1-m. $$

Hence $k=j+m-1$ is impossible unless $m=1$. More directly, the unique value of $k$ for which the numerator does not vanish is exactly the value satisfying

$$ k+1-j=m, $$

namely

$$ k=j+m-1. $$

This value lies in ${1,\dots,n}$ precisely for the single surviving term.

For this value of $k$, we have

$$ 1-j+k-r = 1-j+(j+m-1)-r = m-r. $$

Hence the numerator becomes

$$ \prod_{\substack{1\le r\le n\ r\ne m}}(m-r). $$

The denominator is

$$ \prod_{\substack{1\le r\le n\ r\ne k}}(k-r), \qquad k=j+m-1. $$

We now compare these products carefully. Write

$$ k-r=(j+m-1)-r. $$

Set

$$ s=r-j+1. $$

As $r$ runs through ${1,\dots,n}\setminus{k}$, the variable $s$ runs through ${1,\dots,n}\setminus{m}$. Indeed,

$$ s=m \iff r=j+m-1=k. $$

Therefore

$$ \prod_{\substack{1\le r\le n\ r\ne k}}(k-r) = \prod_{\substack{1\le s\le n\ s\ne m}}(m-s). $$

This is exactly the numerator product. Hence the surviving term equals $1$.

Therefore

$$ f(1-j)=1 \qquad (j=1,\dots,n). $$

Since $f(x)-1$ is a polynomial of degree at most $n-1$ having $n$ distinct roots, we conclude that

$$ f(x)\equiv1. $$

Thus

$$ \sum_{k=1}^n \frac{\displaystyle\prod_{\substack{1\le r\le n\ r\ne m}}(x+k-r)} {\displaystyle\prod_{\substack{1\le r\le n\ r\ne k}}(k-r)} =1. $$

$\square$