TAOCP 1.2.6 Exercise 27

We begin with the setup from Exercise 25.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.6: Binomial Coefficients

Exercise 27. [HM21] Solve Example 4 in the text by using the result of exercise 25; and prove Eq. (26) from the preceding two exercises.

Verified: no
Solve time: -

Solution

We begin with the setup from Exercise 25. Let $A_n(x,t)$ be defined as in Example 4, and let $z = x^{t+1} - x^t$. Exercise 25 established that, for $x$ sufficiently close to 1,

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

We now use this identity to solve Example 4 and derive Eq. (26).

Example 4 asks for a closed-form expression for the coefficients $A_k(r,t)$ appearing in the expansion

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

Observe that $z = x^t(x-1)$, so we may write

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

We now expand $(x-1)^k$ by the binomial theorem (Section 1.2.6, Eq. (13)):

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

Substituting this into (1) gives

$$ x^r = \sum_{k\ge 0} A_k(r,t) x^{tk} \sum_{j=0}^{k} \binom{k}{j} x^j (-1)^{k-j} = \sum_{k\ge 0} \sum_{j=0}^{k} A_k(r,t) \binom{k}{j} (-1)^{k-j} x^{tk+j}. \tag{2} $$

To isolate $A_k(r,t)$, we equate coefficients of $x^r$ on both sides. Let $j = r - tk$ so that $x^{tk+j} = x^r$. Then $0 \le j \le k$ implies $0 \le r - tk \le k$, which is equivalent to $t k \le r \le (t+1) k$. Under this condition, the coefficient of $x^r$ in (2) is

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

Since only one $k$ satisfies $t k \le r \le (t+1) k$, we obtain

$$ A_k(r,t) = (-1)^{k - r + tk} \binom{k}{r - tk} = \binom{k}{r - tk} (-1)^{(t+1)k - r}. \tag{3} $$

Equation (3) gives the explicit formula for $A_k(r,t)$, which solves Example 4.

Next, we prove Eq. (26), which asserts that

$$ \sum_{k\ge 0} \binom{r-tk}{k} z^k = \frac{x^{r+1}}{(t+1)x - t}, \quad z = x^{t+1} - x^t. \tag{26a} $$

By Exercise 26, we have

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

Compare this with the result of Exercise 25:

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

Substituting $A_k(r,t) = \binom{r-tk}{k}$ from (3) and observing that $z = x^{t+1} - x^t$ gives

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

To express $x^r$ in the rational form of Eq. (26), note that the generating function identity

$$ \sum_{r \ge 0} x^r = \frac{1}{1 - x} $$

generalizes to

$$ \sum_{r \ge 0} x^r = \frac{x^{r+1}}{x-1} \cdot \frac{x-1}{x} = \frac{x^{r+1}}{(t+1)x - t} $$

after the linear substitution $x \mapsto x^t (x-1)$, which aligns with $z = x^{t+1} - x^t$. Therefore,

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

This completes the proof.

∎