# Equivalence of Definitions of Stirling Numbers of the Second Kind

## Contents

## 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$

## Also see

- Equivalence of Definitions of Unsigned Stirling Numbers of the First Kind
- Equivalence of Definitions of Signed Stirling Numbers of the First Kind

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $35$