Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Toying with their relation to the falling factorial should work. –  Raskolnikov Apr 20 '11 at 20:14

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
1  
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
1  
@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.)

share|improve this answer
    
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} $$

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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