Sum over k to n of Unsigned Stirling Number of the First Kind of k with m by n factorial over k factorial

Theorem

Let $m, n \in \Z_{\ge 0}$.

$\displaystyle \sum_{k \mathop \le n} \left[{k \atop m}\right] \frac {n!} {k!} = \left[{n + 1 \atop m + 1}\right]$

where:

$\displaystyle \left[{k \atop m}\right]$ denotes an unsigned Stirling number of the first kind
$n!$ denotes a factorial.

Proof

The proof proceeds by induction on $m$.

For all $m \in \Z_{\ge 0}$, let $P \left({m}\right)$ be the proposition:

$\displaystyle \forall n \in \Z_{\ge 0}: \sum_{k \mathop \le n} \left[{k \atop m}\right] \frac {n!} {k!} = \left[{n + 1 \atop m + 1}\right]$

Basis for the Induction

$P \left({0}\right)$ is the case:

 $\displaystyle$  $\displaystyle \sum_{k \mathop \le n} \left[{k \atop 0}\right] \frac {n!} {k!}$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \le n} \delta_{k 0} \frac {n!} {k!}$ Definition of Unsigned Stirling Numbers of the First Kind $\displaystyle$ $=$ $\displaystyle \frac {n!} {0!}$ All terms but where $k = 0$ vanish $\displaystyle$ $=$ $\displaystyle n!$ Definition of Factorial $\displaystyle$ $=$ $\displaystyle \left[{n + 1 \atop 0 + 1}\right]$ Unsigned Stirling Number of the First Kind of n+1 with 1

So $P \left({0}\right)$ is seen to hold.

This is the basis for the induction.

Induction Hypothesis

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

So this is the induction hypothesis:

$\displaystyle \sum_{k \mathop \le n} \left[{k \atop r}\right] \frac {n!} {k!} = \left[{n + 1 \atop r + 1}\right]$

from which it is to be shown that:

$\displaystyle \sum_{k \mathop \le n} \left[{k \atop r + 1}\right] \frac {n!} {k!} = \left[{n + 1 \atop r + 2}\right]$

Induction Step

This is the induction step:

 $\displaystyle$  $\displaystyle \sum_{k \mathop \le n} \left[{k \atop r + 1}\right] \frac {n!} {k!}$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \le n} \left({\left({k - 1}\right) \left[{k - 1 \atop r + 1}\right] + \left[{k - 1 \atop r}\right]}\right) \frac {n!} {k!}$ Definition of Unsigned Stirling Numbers of the First Kind $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \le n} k \left[{k - 1 \atop r + 1}\right] \frac {n!} {k!} - \sum_{k \mathop \le n} \left[{k - 1 \atop r + 1}\right] \frac {n!} {k!} + \sum_{k \mathop \le n} \left[{k - 1 \atop r}\right] \frac {n!} {k!}$ $\displaystyle$ $=$ $\displaystyle \sum_{k \mathop \le n} \left[{k - 1 \atop r + 1}\right] \frac {n!} {\left({k - 1}\right)!} - \sum_{k \mathop \le n} \left[{k - 1 \atop r + 1}\right] \frac {n!} {k!} + \sum_{k \mathop \le n} \left[{k - 1 \atop r}\right] \frac {n!} {k!}$

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

Therefore:

$\displaystyle \forall m, n \in \Z_{\ge 0}: \sum_{k \mathop \le n} \left[{k \atop m}\right] \frac {n!} {k!} = \left[{n + 1 \atop m + 1}\right]$

$\blacksquare$