Stirling number of the first kind: Proof of Recursion formula

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.

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.)

This should go as comment, not as an answer(it doesn't provide additional proof), but is too long for the comment-box and may be interesting anyway.

Your given relation describes a shift of the matrix of Stirlingnumbers 1st kind by a postmultiplikation of the Pascalmatrix: $ S1_0 * P_0 = S1_1 $ where the index indicated a diagonal downshifting. See the matrices $S1_0, P_0,S1_1$ below: $$ \small \begin{matrix} & & & S1_0 & & & | & & & & P_0 & & & | & & & S1_1 & & & \\ 1 & . & . & . & . & . & | & 1 & . & . & . & . & . & | & 1 & . & . & . & . & . \\ -1 & 1 & . & . & . & . & | & 1 & 1 & . & . & . & . & | & . & 1 & . & . & . & . \\ 2 & -3 & 1 & . & . & . & | & 1 & 2 & 1 & . & . & . & | & . & -1 & 1 & . & . & . \\ -6 & 11 & -6 & 1 & . & . & | & 1 & 3 & 3 & 1 & . & . & | & . & 2 & -3 & 1 & . & . \\ 24 & -50 & 35 & -10 & 1 & . & | & 1 & 4 & 6 & 4 & 1 & . & | & . & -6 & 11 & -6 & 1 & . \\ -120 & 274 & -225 & 85 & -15 & 1 & | & 1 & 5 & 10 & 10 & 5 & 1 & | & . & 24 & -50 & 35 & -10 & 1 \end{matrix} $$ This can be iterated, so $ S1_{k+1} = S_k * P_k $

Then the top-left-part of the result becomes -with increasing k - the identity and we can formulate the limit where $n \to \infty$ which extends to the identitymatrix. But this means, that that product of the down-shifted Pascalmatrices equals the inverse of $S1$ (up to dimension n) and on the other hand, the inverse is just the matrix of Stirlingnumbers 2'nd kind. So we get, denoting the top left segment of that matrix $S2$ up to dimension $n$ as $$S2 = \prod_{k=0}^n P_k $$ and the three toplevel segments are $P, P*P_1 , P*P_1*P_2 $ and the third of the three matrices below has its three left columns identical to the matrix of the Stirlingnumbers 2nd kind: $$ \small \begin{matrix} & & & P_0 & & & | & & & & P_0* &P_1 & & | & & P_0* & P_1* & P_2 & & \\ 1 & . & . & . & . & . & | & 1 & . & . & . & . & . & | & 1 & . & . & . & . & . \\ 1 & 1 & . & . & . & . & | & 1 & 1 & . & . & . & . & | & 1 & 1 & . & . & . & . \\ 1 & 2 & 1 & . & . & . & | & 1 & 3 & 1 & . & . & . & | & 1 & 3 & 1 & . & . & . \\ 1 & 3 & 3 & 1 & . & . & | & 1 & 7 & 5 & 1 & . & . & | & 1 & 7 & 6 & 1 & . & . \\ 1 & 4 & 6 & 4 & 1 & . & | & 1 & 15 & 17 & 7 & 1 & . & | & 1 & 15 & 25 & 9 & 1 & . \\ 1 & 5 & 10 & 10 & 5 & 1 & | & 1 & 31 & 49 & 31 & 9 & 1 & | & 1 & 31 & 90 & 52 & 12 & 1 \end{matrix} $$

The both product-representations involving the shifted Pascalmatrices give then a nice generalization of your initial identity to (arbitrarily deep) nested products/sums of binomials for the Stirlingnumbers 1st and 2nd kind (a nice, inexhaustible, resource for homework-assignements, btw ;-) )

[update] I tried to relate to Mike Spivey's second identity. Surprise, we get the Bernoulli-numbers, scaled by factorials instead of binomials.
Denote the diagonalmatrix of factorials $F=diagonal(0!,1!,2!,...)$ and $f=F^{-1}$ and then the factorially scaled matrix of Stirlingnumbers 1st kind, whose c'th column provides the coefficients for the powerseries for $\ln(1+x)^c$, as $fS1F = f* S1 * F $ (this is a similarity scaling of $S1$ ) and the matrix of factorially scaled Bernoulli-numbers as $fBF$ then we get an inverse col/row shift by $ fS1F_1 * fBF = fS1F_0 $

$$ \small \begin{matrix} & & & fS1F_1 & & & | & & & & fBF & & & | & & & fS1F_0 & & & \\ 1 & 0 & 0 & 0 & 0 & 0 & | & 1 & 0 & 0 & 0 & 0 & 0 & | & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & | & -1/2 & 1 & 0 & 0 & 0 & 0 & | & -1/2 & 1 & 0 & 0 & 0 & 0 \\ 0 & -1/2 & 1 & 0 & 0 & 0 & | & 1/12 & -1/2 & 1 & 0 & 0 & 0 & | & 1/3 & -1 & 1 & 0 & 0 & 0 \\ 0 & 1/3 & -1 & 1 & 0 & 0 & | & 0 & 1/12 & -1/2 & 1 & 0 & 0 & | & -1/4 & 11/12 & -3/2 & 1 & 0 & 0 \\ 0 & -1/4 & 11/12 & -3/2 & 1 & 0 & | & -1/720 & 0 & 1/12 & -1/2 & 1 & 0 & | & 1/5 & -5/6 & 7/4 & -2 & 1 & 0 \\ 0 & 1/5 & -5/6 & 7/4 & -2 & 1 & | & 0 & -1/720 & 0 & 1/12 & -1/2 & 1 & | & -1/6 & 137/180 & -15/8 & 17/6 & -5/2 & 1 \end{matrix} $$