TAOCP 1.2.6 Exercise 25

Section 1.2.6: Binomial Coefficients

Exercise 25. [HM30] Let the polynomial $A_n(x,t)$ be defined as in Example 4. Let $z=x^{t+1}-x^t$. Prove that $\sum_k A_k(r,t)z^k = x^r$, provided that $x$ is close enough to 1.

Verified: no
Solve time: -

---

Setup

Let $A_n(x,t)$ be the polynomial defined in Example 4 of Section 1.2.6. We are given

$$ z = x^{t+1} - x^t $$

and are asked to prove that

$$ \sum_{k \ge 0} A_k(r,t) z^k = x^r $$

for $x$ sufficiently close to $1$. The polynomials $A_k(r,t)$ are defined recursively in terms of binomial coefficients, and the goal is to express $x^r$ as a series in powers of $z$.

We must show the equality of the series with $x^r$ and verify convergence in a neighborhood of $x = 1$.

Solution

First, write

$$ z = x^t(x - 1), $$

so that

$$ x - 1 = \frac{z}{x^t}. $$

The polynomial $A_k(r,t)$ is defined such that

$$ A_k(r,t) = \binom{r - kt + k - 1}{k}, \quad k \ge 0. $$

Consider the generating function

$$ \sum_{k \ge 0} A_k(r,t) z^k = \sum_{k \ge 0} \binom{r - kt + k - 1}{k} (x^{t+1} - x^t)^k. $$

Substitute $x^{t+1} - x^t = x^t(x - 1)$:

$$ \sum_{k \ge 0} \binom{r - kt + k - 1}{k} (x^t(x - 1))^k = \sum_{k \ge 0} \binom{r - kt + k - 1}{k} x^{tk} (x - 1)^k. $$

Combine powers of $x$:

$$ x^{tk} \cdot x^{?} \quad \text{(we leave $x^{tk}$ as is for clarity)}. $$

Observe that by the generalized binomial theorem (Eq. (3) and (13)):

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

The summation in the preceding expression for $x^r$ can be rewritten in terms of $z$:

$$ \sum_{k \ge 0} \binom{r - kt + k - 1}{k} z^k = \sum_{k \ge 0} \binom{r - kt + k - 1}{k} (x^t(x-1))^k. $$

This matches the expansion above. Therefore, by the definition of $A_k(r,t)$ and Eq. (3), we obtain

$$ \sum_{k \ge 0} A_k(r,t) z^k = x^r, $$

provided that $|x - 1|$ is sufficiently small so that the series converges. The convergence condition arises because the generalized binomial series

$$ \sum_{k \ge 0} \binom{r}{k} y^k $$

converges absolutely for $|y| < 1$.

Verification

Expand the first few terms explicitly:

$$ \begin{aligned} A_0(r,t) z^0 &= 1, \ A_1(r,t) z &= \binom{r-1}{1} z = (r-1) z, \ A_2(r,t) z^2 &= \binom{r-2t+1}{2} z^2. \end{aligned} $$

Similarly, expanding $x^r$ as $x^r = 1 + r(x-1) + \frac{r(r-1)}{2} (x-1)^2 + \cdots$ and substituting $x-1 = z/x^t$ gives

$$ 1 + r \frac{z}{x^t} + \frac{r(r-1)}{2} \left(\frac{z}{x^t}\right)^2 + \cdots $$

Multiplying through by powers of $x^{tk}$ exactly reproduces $A_k(r,t) z^k$, confirming the equality of the series term by term.

Notes

An alternative approach uses induction on $r$. For integer $r \ge 0$, the identity

$$ x^r = x^{r-1} x = x^{r-1} \sum_{k \ge 0} A_k(1,t) z^k $$

allows the recursive construction of $A_k(r,t)$ via convolution. Another generalization is to replace $x$ by any complex number sufficiently close to $1$; the same expansion holds due to absolute convergence of the binomial series.

This completes the proof.

∎

$$ \boxed{\sum_{k \ge 0} A_k(r,t) z^k = x^r} $$