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.


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}$$



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


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$.

  • $\begingroup$ I still haven't been able to deduce the result, although I have tried to apply the first hint. Also, I have not yet understood how to apply the second hint to the problem. $\endgroup$ – Caleb Owusu-Yianoma Nov 6 '15 at 11:28
  • $\begingroup$ @CKKOY: did you look at the Wikipedia page on the inclusion-exclusion principle, especially the paragraph about surjective functions? $\endgroup$ – Jack D'Aurizio Nov 6 '15 at 14:14
  • $\begingroup$ Ah, no I forgot to do that. Thank you for the reminder. $\endgroup$ – Caleb Owusu-Yianoma Nov 7 '15 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.