# Equivalence of Definitions of Unsigned Stirling Numbers of the First Kind

## Theorem

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

### Definition 1

Unsigned Stirling numbers of the first kind are defined recursively by:

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

### Definition 2

Unsigned Stirling numbers of the first kind are defined as the polynomial coefficients $\displaystyle {n \brack k}$ which satisfy the equation:

$\displaystyle x^{\underline n} = \sum_k \left({-1}\right)^{n - k} {n \brack k} x^k$

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

in the sense that the coefficients of the 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(n)$ be the proposition:

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

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

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

From Unsigned Stirling Number of the First Kind of 0 we have:

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

Hence the result holds for $n = 0$.

### Basis for the Induction

$P(1)$ is the case:

We have:

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

Then:

 $\displaystyle {1 \brack k}$ $=$ $\displaystyle {0 \brack k - 1} + 0 {0 \brack k}$ by hypothesis $\displaystyle$ $=$ $\displaystyle \delta_{0 \paren {k - 1} }$ $\displaystyle$ $=$ $\displaystyle \delta_{1 k}$

Thus, in the expression:

$\displaystyle x^{\underline k} = \sum_k\paren {-1}^{1 - k} {1 \brack k} x^1$

we have:

$\displaystyle \paren {-1}^{1 - k} {1 \brack k} = 1$

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

$\displaystyle \paren {-1}^{1 - k} {1 \brack k} = 0$

That is:

$\displaystyle \paren {-1}^{1 - k} {1 \brack k} = \delta_{1 k}$

Thus $P(1)$ is seen to hold.

This is the basis for the induction.

### Induction Hypothesis

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

So this is the induction hypothesis:

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

from which it is to be shown that:

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

### Induction Step

This is the induction step:

 $\displaystyle x^{\underline {r + 1} }$ $=$ $\displaystyle \paren {x - r} x^{\underline r}$ Definition of Falling Factorial $\displaystyle$ $=$ $\displaystyle \paren {x - r} \sum_k \paren {-1}^{r - k} {r \brack k} x^k$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle x \sum_k \paren {-1}^{r - k} {r \brack k} x^k - r \sum_k \\paren {-1}^{r - k} {r \brack k} x^k$ $\displaystyle$ $=$ $\displaystyle \sum_k \paren {-1}^{r - k} {r \brack k} x x^k + \sum_k \paren {-1}^{r - k + 1} {r \brack k} r x^k$ $x$ and $r$ are constant in this context $\displaystyle$ $=$ $\displaystyle \sum_k \paren {-1}^{r - k} {r \brack k} x^{k + 1} + \sum_k \paren {-1}^{r - k + 1} r {r \brack k} x^k$ $\displaystyle$ $=$ $\displaystyle \sum_k \paren {-1})^{r - k + 1} {r \brack k - 1} x^k + \sum_k \paren {-1}^{r - k + 1} r {r \brack k} x^k$ Translation of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle \sum_k \paren {-1}^{r - k + 1} \paren { {r \brack k - 1} + r {r \brack k} } x^k$ Sum of Summations equals Summation of Sum

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

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

as required.

So $P(r) \implies 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 powers in the expression $\displaystyle x^{\underline n} = \sum_k \paren {-1}^{n - k} {n \brack k} x^k$ are uniquely defined by:
$\displaystyle {n \brack k} = {n - 1 \brack k - 1} + \paren {n - 1} {n - 1 \brack k}$
where $\displaystyle {n \brack k} = \delta_{n k}$ when $k = 0$ or $n = 0$.

$\blacksquare$