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

From ProofWiki
Jump to navigation Jump to search

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$


Sources