Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$

Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to $x$, $\left[ x \atop k \right]$ are the Stirling numbers of the first kind, and ${ k \brace x} $ are the Stirling numbers of the second kind.

The formula is a generalization of the inversion formula since $n=0$ and $d=0$ gives the inversion formula $$ \Delta^d x^0 = \sum_k \left[ x \atop k\right]{ k \brace x + d}(-1)^{x+k} = [x=x+d]=[d=0]$$

I have not found this formula documented anywhere and would be interested in either a reference or a reasonable argument that it is in fact previously unknown. A few proofs are shown in this MSE post.

What follows is the path I took to discovery of this formula, it was fun and interesting to take so I hope it is for you as well.

Use the formula for $x^n$ written using the falling factorial $x^{\underline p}=(x)(x-1)\dots(x-p+1)$ $$x^n = \sum_p { n \brace p}x^{\underline p} \tag{0}$$ Now factor out an $x$ on both sides of the formula $$x^{n-1} = \sum_p { n \brace p}(x-1)^{\underline {p-1}} $$ This leads to a new "first order" formula that works for any $x \gt 1$ $$x^{n} = \sum_p { n+1 \brace p}(x-1)^{\underline {p-1}} \tag{1}$$ If $x>2$ we can factor $(x-1)$ and use the "first order" to find the "second order" equation $$\begin{align} x^{n} &= \frac{x}{x-1}x^n - \frac{1}{x-1}x^n \\ &= \frac{1}{x-1}x^{n+1} - \frac{1}{x-1}x^n \\ &= \frac{1}{x-1}\sum_p { n+2 \brace p}(x-1)^{\underline {p-1}} - \frac{1}{x-1}\sum_p { n+1 \brace p}(x-1)^{\underline {p-1}} \\ &= \frac{1}{x-1}\sum_p \left({ n+2 \brace p} - { n+1 \brace p}\right)(x-1)^{\underline {p-1}}\\ &= \sum_p \left({ n+2 \brace p} - { n+1 \brace p}\right)(x-2)^{\underline {p-2}} \tag{2}\\ \end{align}$$ If the pattern is not obvious yet (it is the alternating signed Stirling numbers of the first kind) it can be done once more--factor $(x-2)$ and use the "second order" equation $$\begin{align} x^{n} =& \phantom{-}\frac{x}{x-2}x^n - \frac{2}{x-2}x^n \\ =& \phantom{-}\frac{1}{x-2}x^{n+1} - \frac{2}{x-2}x^n \\ =& \phantom{-}\frac{1}{x-2}\sum_p \left({ n+3 \brace p} - { n+2 \brace p}\right)(x-2)^{\underline {p-2}} \\ & - \frac{2}{x-2}\sum_p \left({ n+2 \brace p} - { n+1 \brace p}\right)(x-2)^{\underline {p-2}} \\ =& \phantom{-}\frac{1}{x-2}\sum_p \left({ n+3 \brace p} -3{ n+2 \brace p} + 2{ n+1 \brace p}\right)(x-2)^{\underline {p-2}}\\ =& \phantom{-}\sum_p \left({ n+3 \brace p} -3{ n+2 \brace p} + 2{ n+1 \brace p}\right)(x-3)^{\underline {p-3}} \tag{3}\\ \end{align}$$ Now that a pattern of the Stirling numbers is more apparent, we can extrapolate until all factors $x(x-1)\dots 2$ are removed leaving just the factor $1$. Thus the "$(x-1)$ order" equation is $$x^n = \sum_p \left(\sum_{k=1}^{x-1}(-1)^{x+k}\left[x-1 \atop k\right]{ n+k \brace p}\right)(x - x + 1)^{\underline{p-x+1}}$$ Interestingly enough, this extrapolation does not yet reach the final formula since $1^{\underline{p-x+1}}$ has two terms, one when $p=x-1$ and one when $p=x$. It does however provide enough motivation to check the simpler version of the formula, and SUCCESS!

share|improve this question
    
I only just realized that maybe it is ok to go all the way and take the single term $0^{\underline{0}}=1$ which would then give the formula for $d=0$. It is just a weird concept to consider taking a factor of $1$ out and leaving $0$ behind. –  adam W Mar 30 at 3:33

1 Answer 1

It is well known that the differencing operator $\Delta$ behaves nicely in the polynomial basis given by the falling factorials: $\Delta(x^{\underline{k}}) = kx^{\underline{k-1}}$. It's also well known that the Stirling numbers are the coefficients that arise when changing from the basis $\{x^k\}$ to the basis $\{x^{\underline{k}}\}$. So I suspect that this formula follows from well-known techniques, even if it hasn't been noted before.

I suggest checking out the relevant chapter in Graham/Knuth/Patashnik's Concrete Mathematics.

share|improve this answer
    
I thought as much myself, but have not seen it in that book. Note that this formula actually eradicates the power on $x$, as opposed to just changing the basis, even when not applying any difference. –  adam W Mar 30 at 0:27
    
True, and the Stirling number has $x$ in the "denominator", which is very unfamiliar to me. –  Greg Martin Mar 30 at 4:43

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.