TAOCP 1.2.6 Exercise 26

Exercise 26. [HM25] Using the assumptions of the previous exercise, prove that

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

Verified: no
Solve time: -

Solution

Exercise 25 established that, under the assumptions of Example 4,

$$ \sum_k A_k(r,t) z^k = x^r, \qquad z=x^{t+1}-x^t, $$

provided that $x$ is sufficiently close to $1$. By the definition of $A_k(r,t)$ in Example 4,

$$ A_k(r,t)=\frac{r-tk}{r}\binom{r}{k}. $$

Using Eq. (7),

$$ \binom{r-tk}{k} =\frac{r-tk}{r-(t+1)k}\binom{r-(t+1)k}{k}. $$

Hence

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

Therefore Exercise 25, with $r$ replaced by $r+1$, gives

$$ \sum_k \binom{r-tk}{k} z^k = \sum_k A_k(r+1,t) z^k = x^{r+1}. $$

This identity still involves the variable $z$. Since

$$ z=x^{t+1}-x^t=x^t(x-1), $$

we compute

$$ \frac{dz}{dx} =(t+1)x^t-tx^{t-1} =x^{t-1}\bigl((t+1)x-t\bigr). $$

Now differentiate the identity

$$ \sum_k A_k(r+1,t) z^k=x^{r+1} $$

with respect to $x$. By the chain rule,

$$ \sum_k kA_k(r+1,t) z^{k-1}\frac{dz}{dx} =(r+1)x^r. $$

Multiplying by $z$ and substituting $z=x^t(x-1)$ yields

$$ \sum_k kA_k(r+1,t) z^k = \frac{(r+1)x^r z}{dz/dx} = \frac{(r+1)x^r\cdot x^t(x-1)} {x^{t-1}((t+1)x-t)}. $$

Since

$$ kA_k(r+1,t) = k\binom{r-tk}{k}, $$

we obtain

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

Adding this to the original identity

$$ \sum_k \binom{r-tk}{k} z^k=x^{r+1}, $$

after multiplying the latter by

$$ \frac{(t+1)x-t-(r+1)(x-1)}{(t+1)x-t}, $$

gives

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

Therefore

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

This completes the proof.

∎