It has a fairly easy proof; but perhaps this is already known to you?
-
-
Replying to @MathPrinceps
Is there a pretty bijective proof? That’s what I’d really like (and don’t have).
1 reply 0 retweets 1 like -
Replying to @robinhouston
The proof I know is essentially algebraic-inductive. Very straightforward, but perhaps not so illuminating, as is often true of such proofs.
1 reply 0 retweets 1 like -
Replying to @MathPrinceps
I know two proofs. One is to show that both expressions satisfy the recurrence f(n, k+1) = \sum_1^n i f(i, k). The other is to consider the probability that, rolling a fair n-sided die (n+k) times, you see all n sides of the die; and compute this probability in two different ways
1 reply 0 retweets 2 likes -
Replying to @robinhouston @MathPrinceps
If your proof is neither of these, I would love to see it.
1 reply 0 retweets 1 like -
Replying to @robinhouston
My proof is neither of these, and I'm delighted to learn of your proofs, which are probably more satisfactory. I simply show that the Stirling numbers (of the right kind) are the coefficients of the "descending factorial" polynomials, by straightforward algebraic-inductive means.
1 reply 0 retweets 0 likes -
Replying to @MathPrinceps @robinhouston
The essence of the argument is almost mindlessly straightforward: x^2 = x(x - 1) + x, x^3 = [x(x - 1)][(x - 2) + 2] + x[(x - 1) + 1], x^4 = [x(x - 1)(x - 2)][(x - 3) + 3] + [x(x - 1)][(x - 2) + 2] + x[(x - 1) + 1], etc., reveals the required role for the Stirling numbers.
1 reply 0 retweets 1 like -
Replying to @MathPrinceps
I’m afraid the incorrect expression for x^4 is making it hard for me to see the pattern you’re illustrating here. I’m sorry to be so slow. Would you mind giving the expression you intended for x^4?
1 reply 0 retweets 1 like -
Replying to @robinhouston
Did I really get that wrong? Sorry. OK, so you proceed inductively: first, write x^(n-1) as a sum of falling factorials (with Stirling number coefficients), and then get x^n from that sum by multiplying each of its constituent summands by the appropriate [(x - n) + n] factor.
1 reply 0 retweets 0 likes -
Replying to @MathPrinceps @robinhouston
In the case of x^4, it goes like this: x^4 = x[x^3] = x[x(x - 1)(x - 2) + 3x(x - 1) + x] = [x(x - 1)(x - 2)][(x - 3) + 3] + 3[x(x - 1)][(x - 2) + 2] + [x][(x - 1) + 1] = x(x - 1)(x - 2)(x - 3) + 6x(x - 1)(x - 2) + 7x(x - 1) + x. Does that clarify the idea?
1 reply 0 retweets 0 likes
At least this approach shows why the coefficients of the falling factorial polynomials appearing in the sum for x^n must satisfy the same recursion relation obeyed by the Stirling numbers. And since both the recurrence and the initial conditions match, the numbers must, as well.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.