TAOCP 1.2.6 Exercise 21

Exercise 21. [M05] Both sides of Eq. (25) are polynomials in $s$; why isn't that equation an identity in $s$?

Verified: yes
Solve time: 34s

In Eq. (25), if $m$, $n$, and $r$ are regarded as fixed nonnegative integers, each term $\binom{s+k}{n}$ is a polynomial in $s$ of degree $n$ by Eq. (3). Hence the left-hand side is a polynomial in $s$ of degree at most $n$.

The right-hand side is $\binom{r+s+1}{m+n+1}$, which is a polynomial in $s$ of degree $m+n+1$ by Eq. (3). When $m\ge0$, this degree is at least $n+1$. Therefore the two sides cannot be identical as polynomials in the indeterminate $s$, except in trivial special cases. Equation (25) is asserted only for nonnegative integer values of the parameters; it is not an identity in the unrestricted variable $s$. ∎