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

-
Toying with their relation to the falling factorial should work. – Raskolnikov Apr 20 '11 at 20:14

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.

-
Thank you for your response. I looked at the Wikipedia-Article and found that the falling factorial is defined as: $x^{\underline{n}}=\sum_{k=0}^{n}s_{n,k}x^{k}$. I thought of using it like this: $x^{\underline{n+1}}=x\left(x-1\right)^{\underline{n}}=x\sum_{k=0}^{n}s_{n,k}x^{‌​k}$ I am trying to connect the recursion with this formula, but I don't see a link. Am I on a wrong path? Regards, Aufwind – Aufwind Apr 20 '11 at 20:38
@Aufwind: You have made a small mistake when developing the falling factorial. You are applying it on $x-1$, hence, it should also be $x-1$ in the development. – Raskolnikov Apr 20 '11 at 20:46
Ok, I see the mistake. Sorry! =) So it has to be. $x^{\underline{n+1}}=x \left(x-1 \right)^{\underline{n}}=x \sum_{k=0}^{n}s_{n,k} \left(x-1 \right)^{k}$ But what would be the next step? – Aufwind Apr 20 '11 at 20:53
@Aufwind: I made an extra edit. – Raskolnikov Apr 20 '11 at 20:57
@Raskolonikov: Thank you. Didn't see that. I'll try that and report back tomorrow. – Aufwind Apr 20 '11 at 21:00

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

-
The proofs I give here are for unsigned Stirling numbers of the first kind. They can be easily adapted if you want the signed versions. – Mike Spivey Apr 21 '11 at 15:22
Thank you very much for showing how to prove this identity in three different manners. – Aufwind Apr 21 '11 at 16:39

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

-
There has been a lot of work done in the past 20 years on matrices containing combinatorial numbers. In particular, I think the $S1$ and $S2$ factorizations that you give also appear in Cheon and Kim, "Stirling Matrix via Pascal Matrix," Linear Algebra and Its Applications 329:49-59, 2001; and also in Yang and Qiao, "Stirling Matrix and Its Property," International Journal of Applied Mathematics 14(2):145-157, 2003. I don't think I've seen the Bernoulli factorization before, though. If you want to learn more, try searching on "Pascal matrix" or "Stirling matrix." – Mike Spivey Apr 22 '11 at 3:52
@Mike Spivey: Mike, thanks for your references, I'll try to locate them in our lib. The combinatorical matrices were my so-to-say "second encounter" with number-theory which led to a project to catalogize such matrix-relations on my own. (That was a lot of fun, but needs some care to rewrite much of it (see my homepage)) To see, that such heuristics were already studied in more depth is always a good feeling, and to have one -possibly- unknown gem (the bernoulli-number-formula) - how nice! Thanks for your infos. – Gottfried Helms Apr 22 '11 at 7:26
I've put that things together and think, I'll go in some more detail later. But this is offtopic here, so just a link go.helms-net.de/math/binomial_new/03_01_StirlingBernoulli.pdf (not yet linked in the index-page of the site) – Gottfried Helms Apr 22 '11 at 13:50
I updated the text with some more explanative text and examples. go.helms-net.de/math/binomial_new/03_01_StirlingBernoulli.pdf – Gottfried Helms Apr 28 '11 at 3:59