Stirling number of the first kind: Proof of Recursion formula

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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} $$