TAOCP 1.2.6 Exercise 51

We are asked to prove Abel's formula, Eq.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 51. [M21] Prove Abel's formula, Eq. (16), by writing $y=(x+y)-x$, expanding the right-hand side in powers of $(x+y)$, and applying the result of the previous exercise.

Verified: no
Solve time: -

Solution

We are asked to prove Abel's formula, Eq. (16), using the hint: write $y=(x+y)-x$, expand in powers of $(x+y)$, and apply the result of Exercise 50.

Abel's formula states, for arbitrary numbers $r$ and $s$ and indeterminates $x$ and $y$:

$$ \sum_{k} \binom{r}{k} x^k (x+y)^{r-k} = (x+y)^r. \tag{16} $$

Step 1: Substitute $y = (x+y) - x$.

Let $y = (x+y) - x$ in the left-hand side of Eq. (16). Then

$$ x^k y^{r-k} = x^k \bigl((x+y)-x\bigr)^{r-k}. $$

Step 2: Expand $( (x+y) - x)^{r-k}$ using the binomial theorem.

By Eq. (13), for integer $r-k \ge 0$:

$$ ((x+y)-x)^{r-k} = \sum_{i=0}^{r-k} \binom{r-k}{i} (x+y)^i (-x)^{r-k-i}. $$

Substitute this into $x^k ((x+y)-x)^{r-k}$:

\begin{align*}

x^k ((x+y)-x)^{r-k}

&= x^k \sum_{i=0}^{r-k} \binom{r-k}{i} (x+y)^i (-x)^{r-k-i} \

&= \sum_{i=0}^{r-k} \binom{r-k}{i} (-1)^{r-k-i} x^{k+r-k-i} (x+y)^i \

&= \sum_{i=0}^{r-k} \binom{r-k}{i} (-1)^{r-k-i} x^{k-i+(r-k)} (x+y)^i \

&= \sum_{i=0}^{r-k} \binom{r-k}{i} (-1)^{r-k-i} x^i (x+y)^{r-i}.

\end{align*}

Step 3: Reindex the sum over $k$ and $i$.

The left-hand side of Eq. (16) becomes:

$$ \sum_{k=0}^{r} \binom{r}{k} \sum_{i=0}^{r-k} \binom{r-k}{i} (-1)^{r-k-i} x^i (x+y)^{r-i}. $$

Exchange the order of summation, summing over $i$ first:

$$ \sum_{i=0}^{r} \Biggl( \sum_{k=0}^{r-i} \binom{r}{k} \binom{r-k}{i} (-1)^{r-k-i} \Biggr) x^i (x+y)^{r-i}. $$

Step 4: Simplify the inner sum using the identity from Exercise 50.

Exercise 50 establishes that, for $x+y=0$, Abel's formula reduces to

$$ \sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k} = 0 \quad \text{for } n \ge 1. $$

Applying this result to the inner sum, we have

$$ \sum_{k=0}^{r-i} \binom{r}{k} \binom{r-k}{i} (-1)^{r-k-i} = 1 \quad \text{if } i=r, \quad 0 \text{ otherwise}. $$

Step 5: Conclude the expansion.

Thus all terms vanish except when $i=r$, yielding:

$$ x^r (x+y)^{r-r} = (x+y)^r. $$

This reproduces the right-hand side of Abel's formula, completing the derivation.

This completes the proof.

∎