# Correctness of proof for finite sum of Stirling numbers of the first kind

it is known that the finite sum of Stirling numbers of the first kind $s_{n,k}$ is $n!$ as defined below.

$$\sum_{k=0}^{n} s_{n,k} = n!\tag{1}$$

I attempt to prove this by induction, where the base case $n=1$ can be easily proven since we know that $\begin{bmatrix} n\\ n\end{bmatrix} = 1$ and $\begin{bmatrix} n\\ 0\end{bmatrix} = 0$.

Assuming equation $(1)$ holds, we move on now to prove the following:

$$\sum_{k=0}^{n+1} s_{n+1,k} = (n+1)!$$

Starting from the left hand side we have

\begin{align*} \sum_{k=0}^{n+1} s_{n+1,k} &= \sum_{k=0}^{n+1} s_{n,k-1} + ns_{n,k}\\\\ &= \sum_{k=0}^{n+1} s_{n,k-1} + \sum_{k=0}^{n+1} ns_{n,k}\\\\ &= n! + n\sum_{k=0}^{n+1} s_{n,k}\\\\ &= n! + n(n!)\\\\ &= (n+1)!\quad\square\quad\text{(since }s_{n,n+1}=0\text{)} \end{align*}

Is my proof as such correct and rigorous enough?

-
It appears to me that your $\iff$’s are supposed to be equalities; is that right? – Brian M. Scott Feb 12 '13 at 10:36
Yep, thanks! i didn't really know how to get the proper formatting for equations in.. – mercurial Feb 12 '13 at 10:38
I’ll change those, and then you can right-click on the formulas to see what I did. – Brian M. Scott Feb 12 '13 at 10:39
Yes, the calculation for the induction step looks fine, though I’d write $$\sum_{k=0}^{n+1}\left(s_{n,k-1}+ns_{n,k}\right)$$ to avoid any possible misunderstanding about the scope of the summation. – Brian M. Scott Feb 12 '13 at 10:41

## 1 Answer

As often, it all depends on what you consider given. If you consider the recurrence relation as given, your proof looks OK. But that would only really make sense if you know how to prove that recurrence relation without appealing to the fact that $s_{n,k}$ counts the number of permutations of $n$ objects with $k$ cycles, because if you're going to use that fact, you don't need a proof by induction, since it almost immediately implies what you're trying to prove.

-