Stirling number of the first kind: Proof of Recursion formula I want to prove this recursion formula for Stirling numbers of the first kind:
$$s_{n+1,k+1} = \sum_{i=k}^{n} \binom{i}{k} s_{n,i}$$
But I lack a useful idea.  Perhaps someone could inspire me?
Kind regards.
 A: Hint: Using the formula for the falling factorial, note that
$$(x)_{n+1} = x \cdot (x-1)_n \; .$$
Develop the falling factorial in terms of Stirling numbers of the first kind and powers of $(x-1)^k$. Then, use Newton's binomial formula to expand the powers $(x-1)^k$. A bit of rearranging of the terms finishes the proof.
From (note I modified your formula a bit, you'll see that it's easier to recognize the end result)
$$\sum_{i=0}^{n}\sum_{k=0}^{i} s(n,i)\binom{i}{k} (-1)^{i-k} x^{k+1}$$
you can rearrange as
$$\sum_{k=0}^{n}\sum_{i=k}^{n} s(n,i)\binom{i}{k} (-1)^{i-k} x^{k+1} \; .$$
If you don't see this, work out some terms of this double sum explicitly, it should be obvious. Then the left hand side of the falling factorial equation is
$$(x)_{n+1}=\sum_{k=0}^{n+1} s(n+1,k) x^k = \sum_{k=0}^{n} s(n+1,k+1) x^{k+1}$$
Equating left and right hand side, we get
$$s(n+1,k+1) = \sum_{i=k}^{n} s(n,i)\binom{i}{k} (-1)^{i-k} \; .$$
Now, this may seem different from the formula you were required to derive, but that's just because I derived a formula for the signed Stirling numbers of the first kind, whereas yours was probably for unsigned ones. No problem however, just multiply both sides of the equations by $(-1)^{k-n}$ and according to the definition on the wikipage, you will get the end result.
A: Here are three other proof approaches.
First: Show that both sides satisfy the recurrence $R(n,k) = n R(n-1,k) + R(n-1,k-1)$, with boundary condition $R(0,k) = 1$ if $k = 0$ and $0$ otherwise.  
If $R(n,k) = s_{n+1,k+1}$, then the recurrence is clearly satisfied, as this is just the standard recurrence for the Stirling numbers of the first kind.
For the right-hand side, with $R(n,k) = \sum_{i=k}^n \binom{i}{k} s_{n,i}$, use the Stirling recurrence again, reindex one of the sums, and apply the binomial coefficient recurrence.  
All that's left after that is checking the boundary conditions.
Second: Use the generating function $$\sum_{n=0}^{\infty} s_{n,k} \frac{z^n}{n!} = \frac{\left(\ln \left( \frac{1}{1-z} \right) \right)^k}{k!}.$$  (See, for example, Concrete Mathematics, 2nd edition, eq. (7.50) on p. 351.)  Start with the version for $s_{n+1,k+1}$, differentiate both sides, expand the factor of $\frac{1}{1-z}$ using the Taylor series for $e^{\ln (1/(1-z))}$, and apply the generating function again.  (This argument is in Charalambides's Enumerative Combinatorics, p. 296.)
Third: Use a combinatorial argument.  The left-hand side counts the number of permutations of $\{0, 1, \ldots, n\}$ with exactly $k+1$ cycles.  The right-hand side counts the number of permutations of $\{1, 2, \ldots, n\}$ with any number of cycles and in which $k$ of the cycles are distinguished in some way.  Set up a one-to-one correspondence between the two sets by combining the nondistinguished cycles on the right-hand side into one cycle and inserting a $0$ in the right place.  (See, for example, Benjamin and Quinn, Proofs That Really Count, Identity 190, p. 102.)
