# Proving a closed form of $\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k$ (for $0\leq k\le m$).

I'm attempting to show that, given a positive integer $m$ and a non-zero constant $\lambda,$ the sequence $n\mapsto\lambda^nn^k$ satisfies the recurrence relation $$\sum_{j=0}^m\binom{m}{j}(-\lambda)^{m-j}a_{n+j}=0$$ for any integer $0\le k<m.$ I have reduced the problem to showing that $$\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k=0$$ for such $k.$ To prove the $k=0$ case, one need only apply the binomial theorem to $(1-1)^m,$ but I'm stymied trying to prove it for other such $k.$

I checked several examples specifically to make sure I hadn't erred along the way, and it seems that it's true. I also determined (quite by accident) the apparent identity $$\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^m=m!,$$ which I have no idea how to prove, either. This leads me to wonder how one could possibly go about determining a closed form for $f(k,m):=\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k.$

Any suggestions/hints (for finding a closed form, proving the identities, or proving the recurrence relation is satisfied) would be appreciated.

Recall that $[m]=\{1,2,\cdots ,m\}$ and $A^B=\{f:A\longrightarrow B:\text{ f function}\}$.>By inclusion exclusion:

$$\sum_{j=0}^m \binom{m}{j}(-1)^j(m-j)^m=m^m-\sum_{j=1}^m \binom{m}{j}(-1)^{j-1}(m-j)^m=|[m]^{[m]}\setminus \bigcup _{j=1}^m A_j\|,$$ such that $A_x=\{f\in [m]^{[m]}:x\not \in Im(f)\}$ so $|A_x|=(m-1)^m$ and if $x\neq y,$ $A_x\cap A_y=(m-2)^m$ and so on. But that set is nothing more than permutations because are functions from $[m]$ to $m$ that are surjective. And there are $m!$ of them.

• Very nice! I almost can't believe that I missed the combinatorial approach. – Cameron Buie Jul 23 '17 at 20:29

This is (almost) the formula for the Stirling numbers of the second kind which count the partitions of $\{1,\dots,n\}$ into non-empty sets.

They have the generating function

$$\sum_{n,m} \begin{Bmatrix} n \\ m \end{Bmatrix} \frac{x^n}{n!}y^m = \exp(y(e^x - 1)).$$

Then

\begin{align} \begin{Bmatrix} n \\ m \end{Bmatrix} &= \left[ \frac{x^n}{n!}y^m \right] \exp(y(e^x - 1)) \\ &= \frac{1}{m!} \left[ \frac{x^n}{n!} \right] (e^x - 1)^m \\ &= \frac{1}{m!} \left[ \frac{x^n}{n!} \right] \sum_{j = 0}^m \binom{m}{j}e^{jx}(-1)^{m - j} \\ &= \frac{1}{m!} \sum_{j = 0}^m \binom{m}{j}j^n(-1)^{m - j}. \end{align}

So one has

$$\sum_{j = 0}^m \binom{m}{j}j^n(-1)^{m - j} = m! \begin{Bmatrix} n \\ m \end{Bmatrix}.$$

The right hand side evaluates to $0$ when $n < m$ and to $m!$ when $n = m$.


$\ds{{n \brace m}}$ is a Stirling Number of the Second Kind.

Then, \begin{align} \sum_{j = 0}^{m}{m \choose j}(-1)^{m - j}\,j^{k} & = k!\,m!{k \brace m}\,{1 \over k!} = \bbx{m!{k \brace m}} \end{align}

• I'm afraid I don't follow the substitution $j^k=\left\{k!\left[z^k\right]e^{jz}\right\}.$ are the braces and brackets grouping symbols, or indicative of some functions? What is $z$? – Cameron Buie Jul 23 '17 at 15:47
• @CameronBuie $\left[z^{k}\right]\mathrm{f}\left(z\right)$ denotes the coefficient of $z^{k}$ in the $\mathrm{f}\left(z\right)$ expansion in powers of $z$. Note that $\mathrm{e}^{jz} = \sum_{\ell = 0}^{\infty}{j^{\ell}z^{\ell} \over \ell!}$ such that $\left[z^{k}\right]\mathrm{e}^{jz} = {j^{k} \over k!}$. The braces $\left\{\right\}$ is just for grouping... Thanks for your remark. – Felix Marin Jul 23 '17 at 15:57

You don't need to know any combinatorics to solve your original problem, just linear algebra (which happens to have combinatorial consequences). Let $S$ denote the (forward) shift operator, which sends a sequence $a_n$ to the sequence

$$(Sa)_n = a_{n+1}.$$

Saying that a sequence satisfies a linear recurrence $a_{n+k} = c_{k-1} a_{n+k-1} + \dots + c_0 a_n$ is equivalent to saying that it satisfies

$$(S^k - c_{k-1} S^{k-1} - \dots - c_0) a = 0.$$

Here are some simple observations:

1. $a_n = r^n$ satisfies $(S - r) a = 0$.
2. $(S - 1)$ computes the forward difference $(\Delta a)_n = a_{n+1} - a_n$. The forward difference of a polynomial of degree $d$ is a polynomial of degree $d-1$, so it follows that $a_n = n^d$ satisfies $(S - 1)^{d+1} a = 0$.
3. If $a_n = n^k r^n$ then

$$\boxed{ (S - r) a = (n + 1)^k r^{n+1} - n^k r^{n+1} = (\Delta n^k) r^{n+1} }.$$

This is the key computation. Induction gives

$$(S - r)^i a = (\Delta^i n^k) r^{n+i}$$

and hence

$$(S - r)^m a = 0, m \ge k + 1.$$

In fact it's possible to reformulate the entire theory of linear recurrences in terms of the shift operator; basically the point is that you can factor $S^k - c_{k-1} S^{k-1} - \dots$ into irreducible factors, as a polynomial in $S$.

The Stirling numbers appear implicitly in this computation as the value of $\Delta^i n^k$ at $0$. Here are some other notes regarding the patterns that have been described in this discussion so far:

1. $$\Delta^i a = (S - 1)^i a = \sum_{j=0}^i (-1)^{i-j} {i \choose j} S^j a$$
2. If $a_n = c_d n^d + \dots$ is a polynomial of degree $d$ with leading coefficient $c_d$, then $(\Delta a)_n = d c_d n^{d-1} + \dots$ is a polynomial of degree $d-1$ with leading coefficient $dc_d$.
3. Inducting on 5 gives $(\Delta^d n^d) = d!$.