11
$\begingroup$

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.

$\endgroup$
1

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ 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 $\endgroup$
    – Aufwind
    Apr 20, 2011 at 20:38
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 20, 2011 at 20:46
  • $\begingroup$ 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? $\endgroup$
    – Aufwind
    Apr 20, 2011 at 20:53
  • $\begingroup$ @Aufwind: I made an extra edit. $\endgroup$ Apr 20, 2011 at 20:57
  • $\begingroup$ @Raskolonikov: Thank you. Didn't see that. I'll try that and report back tomorrow. $\endgroup$
    – Aufwind
    Apr 20, 2011 at 21:00
9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 21, 2011 at 15:22
  • $\begingroup$ Thank you very much for showing how to prove this identity in three different manners. $\endgroup$
    – Aufwind
    Apr 21, 2011 at 16:39
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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." $\endgroup$ Apr 22, 2011 at 3:52
  • $\begingroup$ @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. $\endgroup$ Apr 22, 2011 at 7:26
  • 1
    $\begingroup$ 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) $\endgroup$ Apr 22, 2011 at 13:50
  • $\begingroup$ I updated the text with some more explanative text and examples. go.helms-net.de/math/binomial_new/03_01_StirlingBernoulli.pdf $\endgroup$ Apr 28, 2011 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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