TAOCP 1.2.6 Exercise 33

We prove the identities by induction on $n$, using the definitions of falling and rising factorial powers and the standard binomial formula for ordinary powers.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 33. [M20] Show that the binomial formula is valid also when it involves factorial powers instead of the ordinary powers. In other words, prove that

$$ (x+y)^{\underline{n}} = \sum_k \binom{n}{k}x^{\underline{k}}y^{\underline{n-k}}, \qquad (x+y)^{\overline{n}} = \sum_k \binom{n}{k}x^{\overline{k}}y^{\overline{n-k}}. $$

Verified: no
Solve time: -

Solution

We prove the identities by induction on $n$, using the definitions of falling and rising factorial powers and the standard binomial formula for ordinary powers.

Part 1: Falling factorials

We define the falling factorial power

$$ x^{\underline{n}} = x(x-1)\cdots(x-n+1),\qquad n \ge 0, $$

with the convention $x^{\underline{0}} = 1$. The standard binomial formula states

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

We show

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

The case $n=0$ is trivial:

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

Suppose the formula holds for some $n \ge 0$. Then

\begin{align*}

(x+y)^{\underline{n+1}} &= (x+y)^{\underline{n}}(x+y-n) \

&= \left[\sum_{k=0}^{n} \binom{n}{k} x^{\underline{k}} y^{\underline{n-k}}\right] (x+y-n) \

&= \sum_{k=0}^{n} \binom{n}{k} \left[ x^{\underline{k}} y^{\underline{n-k}} (x-n + y-n + n? ) \right].

\end{align*}

We simplify carefully. Observe that

$$ x^{\underline{k}} (x - k) = x^{\underline{k+1}},\qquad y^{\underline{n-k}} (y - (n-k)) = y^{\underline{n-k+1}}. $$

Hence

\begin{align*}

x^{\underline{k}} y^{\underline{n-k}} (x+y-n) &= x^{\underline{k+1}} y^{\underline{n-k}} + x^{\underline{k}} y^{\underline{n-k+1}}.

\end{align*}

Therefore

\begin{align*}

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

&= \sum_{k=1}^{n+1} \binom{n}{k-1} x^{\underline{k}} y^{\underline{n+1-k}} + \sum_{k=0}^{n} \binom{n}{k} x^{\underline{k}} y^{\underline{n+1-k}} \

&= \sum_{k=0}^{n+1} \left[\binom{n}{k} + \binom{n}{k-1} \right] x^{\underline{k}} y^{\underline{n+1-k}} \

&= \sum_{k=0}^{n+1} \binom{n+1}{k} x^{\underline{k}} y^{\underline{n+1-k}},

\end{align*}

where the last equality uses the addition formula (9). This completes the induction for falling factorial powers. ∎

Part 2: Rising factorials

We define the rising factorial power

$$ x^{\overline{n}} = x(x+1)\cdots(x+n-1),\qquad n \ge 0, $$

with $x^{\overline{0}} = 1$. Observe the relation

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

Applying the identity for falling factorials, we have

\begin{align*}

(x+y)^{\overline{n}} &= (-1)^n [-(x+y)]^{\underline{n}} \

&= (-1)^n \sum_{k=0}^{n} \binom{n}{k} (-x)^{\underline{k}} (-y)^{\underline{n-k}} \

&= \sum_{k=0}^{n} \binom{n}{k} x^{\overline{k}} y^{\overline{n-k}}.

\end{align*}

This completes the induction for rising factorial powers. ∎

Hence both identities are valid for all integers $n \ge 0$.

$\boxed{(x+y)^{\underline{n}} = \sum_k \binom{n}{k} x^{\underline{k}}y^{\underline{n-k}},\quad (x+y)^{\overline{n}} = \sum_k \binom{n}{k} x^{\overline{k}}y^{\overline{n-k}}}$