# Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$

$$\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!

• 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 '14 at 3:33

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 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 '14 at 0:27
• True, and the Stirling number has $x$ in the "denominator", which is very unfamiliar to me. – Greg Martin Mar 30 '14 at 4:43