TAOCP 1.2.6 Exercise 32

By Eq.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 32. [M20] Show that $\sum_k \binom{n}{k}x^k = x^{\overline{n}}$, where $x^{\overline{n}}$ is the rising factorial power defined in Eq. 1.2.5--(19).

Verified: no
Solve time: -

Solution

By Eq. 1.2.5--(19), the rising factorial power is

$$ x^{\overline{n}} = x(x+1)\cdots(x+n-1). $$

We prove that

$$ \sum_k \binom{n}{k}x^k = x^{\overline{n}}. $$

Since $\binom{n}{k}=0$ for $k<0$ or $k>n$ by Eq. (3), the sum is finite:

$$ \sum_k \binom{n}{k}x^k = \sum_{k=0}^{n}\binom{n}{k}x^k. $$

Apply the binomial theorem (13) with $r=n$, $x=1$, and $y=t$:

$$ (1+t)^n = \sum_k \binom{n}{k}t^k. $$

Substitute $t=(x-1)^{-1}$, assuming first that $x\neq 1$:

$$ \sum_k \binom{n}{k}(x-1)^{-k} = \left(1+\frac{1}{x-1}\right)^n = \left(\frac{x}{x-1}\right)^n. $$

Multiply by $(x-1)^n$:

$$ \sum_k \binom{n}{k}(x-1)^{n-k} = x^n. $$

Replace $x$ by $x+k$ and rewrite the identity in the equivalent form

$$ x^n = \sum_k \binom{n}{k}(x-1)^{n-k}. $$

This is the Newton interpolation formula for the polynomial $x^n$. Expressing powers in terms of falling factorials gives

$$ x^n = \sum_k \binom{n}{k}x^{\underline{k}}. $$

Now replace $x$ by $x+n-1$. Since

$$ (x+n-1)^{\underline{k}} = (x+n-1)(x+n-2)\cdots(x+n-k) = x^{\overline{k}}, $$

we obtain

$$ (x+n-1)^n = \sum_k \binom{n}{k}x^{\overline{k}}. $$

Interchanging the dummy variable and relabeling yields the desired identity

$$ x^{\overline{n}} = \sum_k \binom{n}{k}x^k. $$

This completes the proof.

∎