Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}$

Question

I am working on the following problem:

For each $m$ we have found the values of $$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$ for polynomials of degree at most m.
Use a combinatorial story to find the Stirling number $$m+1 \brace m$$ and deduce a formula for $$\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}.$$

In my Combinatorics lectures, we studied a theorem relating to orthogonality for binomial coefficients. This is what the first sentence of the problem relates to.
So, I know that $$\sum_{j=0}^m {m \choose j}(-1)^j p(j) = \begin{cases} 0 & \text{when $\deg(p)\leq m-1$} \\ (-1)^m m! & \text{when $\deg(p) = m.$} \end{cases}$$

By calculating the result of $m+1 \brace m$ for various values of $m$ ($2, 3$ and $4$, to be precise), I managed to show that $${m+1 \brace m} = {m+1 \choose 2}.$$

However, I am unsure how to solve the very last part of the problem (which requires a deduction).
My main thought about it so far is that: this re-arranged version of the formula for $m+1 \brace m$ $$\sum_{j=0}^m {m \choose j}(-1)^j (m-j)^{m+1} = m! {m+1\choose 2}$$ looks very similar to the formula for the orthogonality for binomial coefficients when $\deg(p) = m$ $$\sum_{j=0}^m {m \choose j}(-1)^j j^{m} = (-1)^m m!.$$ I have not yet been able to relate the two, though.

I would greatly appreciate a hint(s) as to how to solve this last part of the problem.

Answer 1

HINT: If you replace $j$ by $m-j$, you can reduce your equation

$$\sum_{j=0}^m {m \choose j}(-1)^j (m-j)^{m+1} = m! {m+1\choose 2}$$

to

$$\sum_{j=0}^m\binom{m}j(-1)^{m-j}j^{m+1}=m!\binom{m+1}2\;.$$

Now multiply by $(-1)^m$.

Answer 2

Hints: Let $\delta$ be the difference operator $$ \delta : p(x) \longrightarrow p(x)-p(x+1).$$ What happens when we apply $\delta$ to a monomial? Can you check that the degree of $\delta p$ is always one less than the degree of $p$? Can you compare the leading terms of $p(x)$ and $\delta p(x)$? Assuming that the degree of $p$ is $m$, can you prove that $\delta^m p$ is a constant? Which constant?

As an alternative, your last formula can be seen as a consequence of the inclusion-exclusion principle. $m!$ is the number of bijective functions from $A=\{1,\ldots,m\}$ to $A$, and $j^m$ is the number of functions from $A$ to a set with cardinality $j$.