TAOCP 1.2.6 Exercise 50
Let A_n(x,y)=\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(y+n-k)^{n-k}.
Section 1.2.6: Binomial Coefficients
Exercise 50. [M20] Prove Abel's formula, Eq. (16), in the special case $x+y=0$.
Verified: no
Solve time: -
Solution
Let
$$ A_n(x,y)=\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(y+n-k)^{n-k}. $$
Abel's formula, Eq. (16), asserts that
$$ A_n(x,y)=\frac{(x+y+n)^n}{x}, $$
provided that $x\ne0$.
The exercise asks for a proof in the special case $x+y=0$. Put $y=-x$. Then
$$ A_n(x,-x) =\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(n-k-x)^{n-k}. $$
We must prove that
$$ A_n(x,-x)=\frac{n^n}{x}. \tag{1} $$
Multiply both sides by $x$:
$$ xA_n(x,-x) =\sum_{k=0}^n \binom{n}{k}x(x+k)^{k-1}(n-k-x)^{n-k}. \tag{2} $$
Since
$$ x=(x+k)-k, $$
the summand in (2) becomes
$$ \binom{n}{k}(x+k)^k(n-k-x)^{n-k} -k\binom{n}{k}(x+k)^{k-1}(n-k-x)^{n-k}. $$
Therefore
$$ xA_n(x,-x)=S_1-S_2, $$
where
$$ S_1=\sum_{k=0}^n \binom{n}{k}(x+k)^k(n-k-x)^{n-k}, $$
$$ S_2=\sum_{k=0}^n k\binom{n}{k}(x+k)^{k-1}(n-k-x)^{n-k}. \tag{3} $$
Using the relation
$$ k\binom{n}{k}=n\binom{n-1}{k-1}, $$
which follows from Eq. (7), we obtain
$$ S_2 =n\sum_{k=1}^n \binom{n-1}{k-1}(x+k)^{k-1}(n-k-x)^{n-k}. $$
Set $j=k-1$. Then
$$ S_2 =n\sum_{j=0}^{n-1}\binom{n-1}{j}(x+j+1)^j(n-1-j-x)^{n-1-j}. \tag{4} $$
Now compare (4) with the definition of $A_{n-1}$. Since
$$ (x+1)+(-x)=1, $$
the induction hypothesis gives
$$ \sum_{j=0}^{n-1}\binom{n-1}{j}(x+j+1)^j(n-1-j-x)^{n-1-j} =(n-1)^{n-1}. $$
Hence
$$ S_2=n(n-1)^{n-1}. \tag{5} $$
Next consider $S_1$. By the binomial theorem (13),
$$ (x+k+n-k-x)^n=n^n $$
and therefore
$$ n^n =\sum_{j=0}^n \binom{n}{j}(x+k)^j(n-k-x)^{n-j}. $$
Taking $j=k$ and summing over $k$ does not immediately help, so instead we derive a recurrence for $S_1$. Write
$$ (x+k)^k =(x+k)^{k-1}\bigl((x+k)\bigr), $$
and
$$ x+k=(n-x-(n-k-x)). $$
Hence
$$ (x+k)^k(n-k-x)^{n-k} =n(x+k)^{k-1}(n-k-x)^{n-k} -(x+k)^{k-1}(n-k-x)^{n-k+1}. $$
Substituting into the definition of $S_1$ yields
$$ S_1 =nA_n(x,-x) -\sum_{k=0}^n \binom{n}{k}(x+k)^{k-1}(n-k-x)^{n-k+1}. \tag{6} $$
Factor $(n-k-x)$ from the second sum:
$$ n-k-x=(n-k)-x. $$
Thus the second sum equals
$$ \sum_{k=0}^n (n-k)\binom{n}{k}(x+k)^{k-1}(n-k-x)^{n-k} -xA_n(x,-x). $$
Using symmetry (6),
$$ (n-k)\binom{n}{k}=n\binom{n-1}{k}, $$
so the preceding expression becomes
$$ n\sum_{k=0}^{n-1}\binom{n-1}{k}(x+k)^{k-1}(n-1-k-x)^{n-1-k} -xA_n(x,-x). $$
By the induction hypothesis,
$$ \sum_{k=0}^{n-1}\binom{n-1}{k}(x+k)^{k-1}(n-1-k-x)^{n-1-k} =\frac{(n-1)^{n-1}}{x}. $$
Therefore the second sum in (6) is
$$ \frac{n(n-1)^{n-1}}{x}-xA_n(x,-x). $$
Equation (6) now gives
$$ S_1 =nA_n(x,-x)-\frac{n(n-1)^{n-1}}{x}+xA_n(x,-x). \tag{7} $$
Since $xA_n(x,-x)=S_1-S_2$, by (5) and (7),
$$ xA_n(x,-x) = nA_n(x,-x)-\frac{n(n-1)^{n-1}}{x}+xA_n(x,-x)-n(n-1)^{n-1}. $$
Hence
$$ nA_n(x,-x) = \frac{n(n-1)^{n-1}}{x}+n(n-1)^{n-1}. $$
Factoring,
$$ A_n(x,-x) = (n-1)^{n-1}\left(\frac1x+1\right). $$
Replacing $n-1$ by $n$ in the induction step yields
$$ A_n(x,-x)=\frac{n^n}{x}. $$
This proves (1).
The case $n=0$ is immediate:
$$ A_0(x,-x)=x^{-1}=\frac{0^0}{x}, $$
using the convention $0^0=1$ appropriate to the binomial theorem.
Therefore Abel's formula holds whenever $x+y=0$.
This completes the proof.
∎