Summation over Lower Index of Unsigned Stirling Numbers of the First Kind with Alternating Signs

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{\ge 0}$ be a positive integer.

Then:

$\displaystyle \sum_k \left({-1}\right)^k \left[{n \atop k}\right] = \delta_{n 0} - \delta_{n 1}$

where:

$\displaystyle \left[{n \atop k}\right]$ denotes an unsigned Stirling number of the first kind
$\delta_{n 0}$ denotes the Kronecker delta.


Proof

The proof proceeds by induction on $n$.


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

$\displaystyle \sum_k \left({-1}\right)^k \left[{n \atop k}\right] = \delta_{n 0} - \delta_{n 1}$


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

\(\displaystyle \sum_k \left({-1}\right)^k \left[{0 \atop k}\right]\) \(=\) \(\displaystyle \sum_k \delta_{0 k}\) Unsigned Stirling Number of the First Kind of 0
\(\displaystyle \) \(=\) \(\displaystyle 1\) all terms vanish but for $k = 0$
\(\displaystyle \) \(=\) \(\displaystyle \delta_{0 0} - \delta_{0 1}\) Definition of Kronecker Delta

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


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

\(\displaystyle \sum_k \left({-1}\right)^k \left[{1 \atop k}\right]\) \(=\) \(\displaystyle \sum_k \left({-1}\right)^k \delta_{1 k}\) Unsigned Stirling Number of the First Kind of 1
\(\displaystyle \) \(=\) \(\displaystyle -1\) all terms vanish but for $k = 1$
\(\displaystyle \) \(=\) \(\displaystyle \delta_{1 0} - \delta_{1 1}\) Definition of Kronecker Delta

Thus $P \left({1}\right)$ is seen to hold.


Basis for the Induction

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

\(\displaystyle \sum_k \left({-1}\right)^k \left[{2 \atop k}\right]\) \(=\) \(\displaystyle -\left[{2 \atop 1}\right] + \left[{2 \atop 2}\right]\) Definition of Summation
\(\displaystyle \) \(=\) \(\displaystyle -\left[{2 \atop 1}\right] + 1\) Unsigned Stirling Number of the First Kind of Number with Self
\(\displaystyle \) \(=\) \(\displaystyle -\binom 2 2 + 1\) Unsigned Stirling Number of the First Kind of n with n-1
\(\displaystyle \) \(=\) \(\displaystyle -1 + 1\) Binomial Coefficient with Self
\(\displaystyle \) \(=\) \(\displaystyle 0\) Binomial Coefficient with Self
\(\displaystyle \) \(=\) \(\displaystyle \delta_{2 0} - \delta_{2 1}\) Definition of Kronecker Delta

Thus $P \left({2}\right)$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

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


So this is the induction hypothesis:

$\displaystyle \sum_k \left({-1}\right)^k \left[{m \atop k}\right] = \delta_{m 0} - \delta_{m 1} = 0$


from which it is to be shown that:

$\displaystyle \sum_k \left({-1}\right)^k \left[{m + 1 \atop k}\right] = \delta_{\left({m + 1}\right) 0} - \delta_{\left({m + 1}\right) 1} = 0$


Induction Step

This is the induction step:


\(\displaystyle \sum_k \left({-1}\right)^k \left[{m + 1 \atop k}\right]\) \(=\) \(\displaystyle \sum_k \left({-1}\right)^k \left({m \left[{m \atop k}\right] + \left[{m \atop k - 1}\right]}\right)\) Definition of Unsigned Stirling Numbers of the First Kind
\(\displaystyle \) \(=\) \(\displaystyle m \sum_k \left({-1}\right)^k \left[{m \atop k}\right] + \sum_k \left({-1}\right)^k \left[{m \atop k - 1}\right]\)
\(\displaystyle \) \(=\) \(\displaystyle m \sum_k \left({-1}\right)^k \left[{m \atop k}\right] - \sum_k \left({-1}\right)^k \left[{m \atop k}\right]\) Translation of Index Variable of Summation
\(\displaystyle \) \(=\) \(\displaystyle \left({m - 1}\right) \sum_k \left[{m \atop k}\right]\)
\(\displaystyle \) \(=\) \(\displaystyle \left({m + 1}\right) \times 0\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle 0\)


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


Therefore:

$\displaystyle \forall n \in \Z_{\ge 0}: \sum_k \left({-1}\right)^k \left[{n \atop k}\right] = \delta_{n 0} - \delta_{n 1}$

$\blacksquare$


Sources