Kvant Math Problem 184

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m19s
Source on kvant.digital

Problem

Prove the identity $$\dfrac{C^0_n}{x} - \dfrac{C^1_n}{x + 1} + ... + (-1)^n\dfrac{C^n_n}{x + n} = \dfrac{n!}{x(x+1)(x+2)...(x+n)}.$$

G. E. Esipenko

Exploration

The expression is a finite alternating sum of simple fractions with shifts in the denominator. The right-hand side is a single rational function with denominator $x(x+1)\cdots(x+n)$. This strongly suggests a partial fraction decomposition of the right-hand side into terms of the form $\frac{1}{x+k}$.

A natural approach is to multiply both sides by the common denominator $P_n(x)=x(x+1)\cdots(x+n)$ and compare the resulting expressions as polynomials in $x$. After clearing denominators, each term on the left becomes a product of $n$ linear factors, and the entire expression becomes a polynomial of degree at most $n$.

Evaluating the resulting polynomial at special points $x=-m$, where one factor of $P_n(x)$ vanishes, isolates a single term in the sum. This produces factorial expressions, and the binomial coefficient structure suggests cancellation leading to a constant value independent of $m$.

The key point is verifying that the resulting polynomial is constant by checking it agrees at $n+1$ distinct points.

Problem Understanding

This is a Type B problem, requiring a proof of an identity between a finite alternating sum of shifted reciprocals and a closed-form rational function.

The central difficulty is to recognize that both sides represent the same rational function and that the left-hand side is its partial fraction decomposition. The strategy is to eliminate denominators and reduce the statement to an identity of polynomials evaluated at enough points to force equality.

Proof Architecture

Define $P_n(x)=x(x+1)\cdots(x+n)$ and multiply both sides of the identity by $P_n(x)$.

A lemma establishes that the resulting expression on the left becomes a polynomial of degree at most $n$.

A second lemma evaluates this polynomial at $x=-m$ for $m=0,1,\dots,n$ and shows that all these values equal $n!$.

A final lemma states that a polynomial of degree at most $n$ that takes the same value at $n+1$ distinct points is constant, hence equal to $n!$.

The most delicate step is the evaluation at $x=-m$, where careful handling of signs in the product $\prod_{j\ne m}(j-m)$ is required.

Solution

Let

$$P_n(x)=x(x+1)\cdots(x+n).$$

Define

$$S_n(x)=\sum_{k=0}^n (-1)^k \frac{\binom{n}{k}}{x+k}.$$

We multiply by $P_n(x)$ and consider

$$T_n(x)=P_n(x),S_n(x)=\sum_{k=0}^n (-1)^k \binom{n}{k}\frac{P_n(x)}{x+k}.$$

For each fixed $k$, the quotient $\frac{P_n(x)}{x+k}$ equals the product of all factors $(x+j)$ with $j\ne k$, hence is a polynomial of degree $n$. Therefore $T_n(x)$ is a polynomial of degree at most $n$.

We evaluate $T_n(x)$ at $x=-m$ for $m\in{0,1,\dots,n}$. In $P_n(x)$, the factor $x+m$ vanishes, so in the sum only the term with $k=m$ survives. Thus

$$T_n(-m)=(-1)^m \binom{n}{m}\prod_{\substack{j=0\ j\ne m}}^n (j-m).$$

The product splits as

$$\prod_{\substack{j=0\ j\ne m}}^n (j-m) =\left(\prod_{j=0}^{m-1}(j-m)\right)\left(\prod_{j=m+1}^{n}(j-m)\right).$$

For $j<m$ each factor satisfies $j-m=-(m-j)$, hence

$$\prod_{j=0}^{m-1}(j-m)=(-1)^m m!.$$

For $j>m$ one has

$$\prod_{j=m+1}^{n}(j-m)=(n-m)!.$$

Therefore

$$\prod_{\substack{j=0\ j\ne m}}^n (j-m)=(-1)^m m!(n-m)!.$$

Substituting this into $T_n(-m)$ gives

$$T_n(-m)=(-1)^m \binom{n}{m} (-1)^m m!(n-m)!.$$

The signs cancel, and using $\binom{n}{m}=\frac{n!}{m!(n-m)!}$ yields

$$T_n(-m)=n!.$$

Thus $T_n(x)$ is a polynomial of degree at most $n$ taking the same value $n!$ at the $n+1$ distinct points $0,-1,\dots,-n$. A polynomial of degree at most $n$ that agrees with a constant at $n+1$ distinct points must equal that constant identically, hence

$$T_n(x)=n!.$$

Dividing by $P_n(x)$ gives

$$S_n(x)=\frac{n!}{x(x+1)\cdots(x+n)}.$$

This completes the proof. ∎

Verification of Key Steps

The decisive step is the computation of $\prod_{j\ne m}(j-m)$. Splitting indices into $j<m$ and $j>m$ produces two independent products, and each contributes a factorial term with a precise sign. The sign from the first block is $(-1)^m$, coming from $m$ negative factors, while the second block contributes no sign since all terms are positive. This yields $(-1)^m m!(n-m)!$ without ambiguity.

The second delicate point is the conclusion that a degree at most $n$ polynomial is determined by its values at $n+1$ points. This uses only the fact that a nonzero polynomial of degree at most $n$ has at most $n$ distinct roots, so a difference of two such polynomials vanishing at $n+1$ points must be identically zero.

The third check is the cancellation

$$(-1)^m \binom{n}{m} (-1)^m m!(n-m)!,$$

where both sign factors are identical and cancel before substituting the binomial coefficient, leaving exactly $n!$ independent of $m$.

Alternative Approaches

A direct partial fraction decomposition of $\frac{n!}{x(x+1)\cdots(x+n)}$ yields residues at $x=-k$ equal to $(-1)^k\binom{n}{k}$, producing the same identity without evaluating the polynomial at multiple points. Another approach uses induction on $n$, splitting the right-hand side into a telescoping difference of two consecutive products, though this requires more algebraic manipulation than the interpolation argument used above.