TAOCP 1.2.6 Exercise 35

We are asked to prove the addition formulas (46) for Stirling numbers directly from their definitions, Eqs.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 35. [M23] Prove the addition formulas (46) for Stirling numbers directly from the definitions, Eqs. (44) and (45).

Verified: no
Solve time: -

Solution

We are asked to prove the addition formulas (46) for Stirling numbers directly from their definitions, Eqs. (44) and (45). For clarity, we restate these definitions.

The Stirling numbers of the first kind, $c(n,k)$, are defined by

$$ x^{\underline{n}} = \sum_{k=0}^{n} c(n,k) x^k, \tag{44} $$

where $x^{\underline{n}} = x(x-1)\cdots(x-n+1)$ is the falling factorial. The Stirling numbers of the second kind, $S(n,k)$, are defined by

$$ x^n = \sum_{k=0}^{n} S(n,k) x^{\underline{k}}. \tag{45} $$

The addition formulas (46) are

$$ c(n+1,k) = n, c(n,k) + c(n,k-1), \qquad S(n+1,k) = k, S(n,k) + S(n,k-1). \tag{46} $$

We prove each formula separately.

1. Stirling numbers of the first kind

Starting from the definition (44),

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

Expanding $x^{\underline{n}}$ by (44), we have

$$ x^{\underline{n}} = \sum_{k=0}^{n} c(n,k) x^k. $$

Therefore,

$$ \begin{aligned} x^{\underline{n+1}} &= (x^{\underline{n}})(x-n) \ &= \left( \sum_{k=0}^{n} c(n,k) x^k \right) (x-n) \ &= \sum_{k=0}^{n} c(n,k) x^{k+1} - \sum_{k=0}^{n} n, c(n,k) x^k \ &= \sum_{k=1}^{n+1} c(n,k-1) x^k - \sum_{k=0}^{n} n, c(n,k) x^k \ &= c(n,0) x^1 - n, c(n,0) x^0 + \sum_{k=1}^{n} \bigl(c(n,k-1) - n, c(n,k)\bigr) x^k + c(n,n) x^{n+1}. \end{aligned} $$

Comparing coefficients of $x^k$ in the expansion

$$ x^{\underline{n+1}} = \sum_{k=0}^{n+1} c(n+1,k) x^k, $$

we find

$$ c(n+1,k) = n, c(n,k) + c(n,k-1), \quad 0 \le k \le n+1, $$

with the convention $c(n,-1) = c(n,n+1) = 0$. This is exactly the addition formula for the first kind.

2. Stirling numbers of the second kind

Starting from the definition (45),

$$ x^{n+1} = x \cdot x^n. $$

Expanding $x^n$ by (45), we have

$$ x^n = \sum_{k=0}^{n} S(n,k) x^{\underline{k}}. $$

Thus,

$$ \begin{aligned} x^{n+1} &= x \sum_{k=0}^{n} S(n,k) x^{\underline{k}} \ &= \sum_{k=0}^{n} S(n,k) , x , x^{\underline{k}} \ &= \sum_{k=0}^{n} S(n,k) \bigl( x^{\underline{k+1}} + k, x^{\underline{k}} \bigr) \ &= \sum_{k=1}^{n+1} S(n,k-1) x^{\underline{k}} + \sum_{k=0}^{n} k, S(n,k) x^{\underline{k}} \ &= \sum_{k=0}^{n+1} \bigl( k, S(n,k) + S(n,k-1) \bigr) x^{\underline{k}}. \end{aligned} $$

Comparing coefficients of $x^{\underline{k}}$ with the definition

$$ x^{n+1} = \sum_{k=0}^{n+1} S(n+1,k) x^{\underline{k}}, $$

we obtain

$$ S(n+1,k) = k, S(n,k) + S(n,k-1), \quad 0 \le k \le n+1, $$

with the convention $S(n,-1) = S(n,n+1) = 0$. This is exactly the addition formula for the second kind.

-, Both addition formulas (46) follow directly from the respective definitions by expanding the $(n+1)$-st power in terms of the $n$-th powers and comparing coefficients.

This completes the proof.

∎