Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.