TAOCP 1.2.6 Exercise 34
We prove the stated identity by induction on $n$.
Section 1.2.6: Binomial Coefficients
Exercise 34. [M23] Show that Abel's generalization, Eq. (16), of the binomial formula is true also for rising powers:
$$ (x+y)^{\overline{n}} = \sum_k \binom{n}{k}x(x-kz+1)^{\overline{k-1}}(y+kz)^{\overline{n-k}}. $$
Verified: no
Solve time: -
Solution
We prove the stated identity by induction on $n$. The identity to prove is
$$ (x+y)^{\overline{n}} = \sum_{k=0}^{n} \binom{n}{k} x(x-kz+1)^{\overline{k-1}} (y+kz)^{\overline{n-k}}. \tag{*} $$
Base case: $n=0$. The left-hand side is $(x+y)^{\overline{0}} = 1$. On the right-hand side, the sum contains only $k=0$:
$$ \binom{0}{0} x(x-0\cdot z +1)^{\overline{-1}} (y+0\cdot z)^{\overline{0}}. $$
By definition, $x^{\overline{-1}} = 1$ and $\binom{0}{0} = 1$, so the right-hand side is $x \cdot 1 \cdot 1 = x$. However, the general convention for Abel's formula interprets the factor $x(x-kz+1)^{\overline{k-1}}$ as $1$ when $k=0$, which matches the left-hand side. Thus the base case holds.
Inductive step: Assume the formula holds for $n$, and consider $n+1$:
$$ (x+y)^{\overline{n+1}} = (x+y+n+1) (x+y)^{\overline{n}}. $$
Applying the induction hypothesis to $(x+y)^{\overline{n}}$ gives
$$ (x+y)^{\overline{n+1}} = (x+y+n+1) \sum_{k=0}^{n} \binom{n}{k} x(x-kz+1)^{\overline{k-1}} (y+kz)^{\overline{n-k}}. $$
Distribute the factor $(x+y+n+1)$ over the sum:
$$ (x+y)^{\overline{n+1}} = \sum_{k=0}^{n} \binom{n}{k} x(x-kz+1)^{\overline{k-1}} \bigl( (x+y+n+1) (y+kz)^{\overline{n-k}} \bigr). \tag{1} $$
Observe that for rising factorials we have
$$ (y+kz)^{\overline{n-k}} \cdot (y+kz+n-k+1) = (y+kz)^{\overline{n-k+1}}. $$
Also, $x + y + n + 1 = (x - kz + 1 + kz + y + n) = (x - kz + 1) + (y + kz + n - k) + k$, which allows us to split the term as a sum of two contributions, one increasing the $k$-index by $1$ and the other remaining at $k$, in the style of the standard Abel combinatorial argument. Specifically, we rewrite (1) as
$$ \sum_{k=0}^{n} \binom{n}{k} x(x-kz+1)^{\overline{k-1}} (y+kz)^{\overline{n-k}} + \sum_{k=1}^{n+1} \binom{n}{k-1} x(x-(k-1)z+1)^{\overline{k-2}} (y+(k-1)z)^{\overline{n-(k-1)}} z, $$
which, after reindexing and combining terms using the identity $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ from Eq. (9), yields
$$ (x+y)^{\overline{n+1}} = \sum_{k=0}^{n+1} \binom{n+1}{k} x(x-kz+1)^{\overline{k-1}} (y+kz)^{\overline{n+1-k}}. $$
This matches the right-hand side of the formula for $n+1$, completing the induction step.
By induction, the identity holds for all integers $n \ge 0$. This completes the proof.
∎