# Equivalence of Definitions of Stirling Numbers of the Second Kind

## Theorem

The following definitions of the concept of Stirling Numbers of the Second Kind are equivalent:

### Definition 1

Stirling numbers of the second kind are defined recursively by:

$\displaystyle {n \brace k} := \begin{cases} \delta_{n k} & : k = 0 \text{ or } n = 0 \\ & \\ \displaystyle {n - 1 \brace k - 1} + k {n - 1 \brace k} & : \text{otherwise} \\ \end{cases}$

### Definition 2

Stirling numbers of the second kind are defined as the coefficients $\displaystyle {n \brace k}$ which satisfy the equation:

$\displaystyle x^n = \sum_k {n \brace k} x^{\underline k}$

where $x^{\underline k}$ denotes the $k$th falling factorial of $x$.

in the sense that the coefficients of the falling factorial powers in the summand are uniquely defined by the given recurrence relation.

## Proof

The proof proceeds by induction.

For all $n \in \N_{> 0}$, let $P \left({n}\right)$ be the proposition:

the coefficients of the falling factorial powers in the expression $\displaystyle x^n = \sum_k {n \brace k} x^{\underline k}$ are uniquely defined by $\displaystyle {n \brace k} = {n - 1 \brace k - 1} + k {n - 1 \brace k}$

where $\displaystyle {n \brace k} = \delta_{n k}$ where $k = 0$ or $n = 0$.

First the case where $n = 0$ is attended to.

We have:

 $\displaystyle x^0$ $=$ $\displaystyle 1$ Definition of Integer Power $\displaystyle$ $=$ $\displaystyle x^{\underline 0}$ Number to Power of Zero Falling is One $\displaystyle$ $=$ $\displaystyle \sum_k \delta_{0 k} x^{\underline k}$ Definition of Kronecker Delta

Thus, in the expression:

$\displaystyle x^0 = \sum_k {0 \brace k} x^{\underline k}$

we have:

$\displaystyle {0 \brace 0} = 1$

and for all $k \in \Z_{>0}$:

$\displaystyle {0 \brace k} = 0$

That is:

$\displaystyle {0 \brace k} = \delta_{0 k}$

Hence the result holds for $n = 0$.

### Basis for the Induction

$\map P 1$ is the case:

We have:

 $\displaystyle x^1$ $=$ $\displaystyle x$ Definition of Integer Power $\displaystyle$ $=$ $\displaystyle x^{\underline 1}$ Number to Power of One Falling is Itself $\displaystyle$ $=$ $\displaystyle \sum_k \delta_{1 k} x^{\underline k}$ Definition of Kronecker Delta

Then:

 $\displaystyle {1 \brace k}$ $=$ $\displaystyle {0 \brace k - 1} + k {0 \brace k}$ by hypothesis $\displaystyle$ $=$ $\displaystyle \delta_{0 \paren {k - 1} } + k \delta_{0 k}$ by hypothesis $\displaystyle$ $=$ $\displaystyle \delta_{0 \paren {k - 1} }$ as $k \delta_{0 k} = 0$ for all $k$ $\displaystyle$ $=$ $\displaystyle \delta_{1 k}$

Thus, in the expression:

$\displaystyle x^1 = \sum_k {1 \brace k} x^{\underline k}$

we have:

$\displaystyle {1 \brace 1} = 1$

and for all $k \in \Z$ where $k \ne 1$:

$\displaystyle {1 \brace k} = 0$

That is:

$\displaystyle {1 \brace k} = \delta_{1 k}$

Thus $\map P 1$ is seen to hold.

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that, if $\map P r$ is true, where $r \ge 1$, then it logically follows that $\map P {r + 1}$ is true.

So this is the induction hypothesis:

The coefficients in the expression $\displaystyle x^r = \sum_k {r \brace k} x^{\underline k}$ are uniquely defined by $\displaystyle {r \brace k} = {r - 1 \brace k - 1} + k {r - 1 \brace k}$

from which it is to be shown that:

The coefficients in the expression $\displaystyle x^{r + 1} = \sum_k {r + 1 \brace k} x^{\underline k}$ are uniquely defined by $\displaystyle {r + 1 \brace k} = {r \brace k - 1} + k {r \brace k}$

### Induction Step

This is the induction step:

Anticipating the expected result, we use $\displaystyle {r + 1 \brace k}$ to denote the coefficients of the $k$th falling factorial power in the expansion of $x^{r + 1}$.

Thus:

 $\displaystyle x^{r + 1}$ $=$ $\displaystyle x x^r$ $\displaystyle$ $=$ $\displaystyle x \left({\sum_k {r \brace k} x^{\underline k} }\right)$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle \sum_k {r \brace k} x x^{\underline k}$ $x$ is constant in this context $\displaystyle$ $=$ $\displaystyle \sum_k {r \brace k} \paren {x^{\underline {k + 1} } + k x^{\underline k} }$ Product of Number by its Falling Factorial $\displaystyle$ $=$ $\displaystyle \sum_k {r \brace k} x^{\underline {k + 1} } + \sum_k {r \brace k} k x^{\underline k}$ Sum of Summations equals Summation of Sum $\displaystyle$ $=$ $\displaystyle \sum_k {r \brace k - 1} x^{\underline k} + \sum_k {r \brace k} k x^{\underline k}$ Translation of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle \sum_k \paren { {r \brace k - 1} x^{\underline k} + {r \brace k} k x^{\underline k} }$ Sum of Summations equals Summation of Sum $\displaystyle$ $=$ $\displaystyle \sum_k \paren { {r \brace k - 1} + k {r \brace k} } x^{\underline k}$

Thus the coefficients of the falling factorial powers are defined by the recurrence relation:

$\displaystyle {r + 1 \brace k} = {r \brace k - 1} + k {r \brace k}$

as required.

So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

for all $n \in \Z_{\ge 0}$, the coefficients of the falling factorial powers in the expression $\displaystyle x^n = \sum_k {n \brace k} x^{\underline k}$ are uniquely defined by:
$\displaystyle {n \brace k} = {n - 1 \brace k - 1} + k {n - 1 \brace k}$
where $\displaystyle {n \brace k} = \delta_{n k}$ where $k = 0$ or $n = 0$.

$\blacksquare$