Proof of an identity of $n!$

Question

I came up (numerically) with an identity concerning n! and I was wondering about a proof of it. Here it is:

\begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \quad \forall n \in \mathbb{Z}^+ \quad \forall k \in \mathbb{R} \\\\ \end{align} (one line edit) I apologise for first accidentally writing $(-n)^n$ instead of $(-r)^n$, as I should have.

For simplicity, k can be set to 0 to yield:

\begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(-r)^n } \\\\ \end{align}

I derived this equation based on that it seems to be the case that nth difference of a polynomial in the form \begin{align} y &= x^n \end{align} always ends up being n!. The origin of k is that it is the initial position from which I started taking the difference, but I left in as I thought it interesting that it cancels out completely. I know Calculus suggests it, but is there a way to prove it without calculus (my goal was to do it while keeping the difference in x constant, ie (x+d)^n - x^n, where d stays 1 preferrably)? So far my attempts yield nested sums.

I am not anything close to a mathematician, so I apologise if this is extremely trivial. Thank you.

Answer 1

Let $\displaystyle P(x)=\sum_{r=0}^n (-1)^r\binom{n}{r}(x-r)^n$; we want to show that $P(x)=n!$.

Since $\displaystyle P(x)=\sum_{r=0}^n(-1)^r\binom{n}{r}\bigg[\sum_{j=0}^n\binom{n}{j}(-r)^jx^{n-j}\bigg]=\sum_{j=0}^n (-1)^j\binom{n}{j}\bigg[\sum_{r=0}^n(-1)^r\binom{n}{r}r^j\bigg]x^{n-j}$,

it suffices to show that $\displaystyle\sum_{r=0}^n(-1)^r\binom{n}{r}r^j=0$ for $0\le j\le n-1$, $\;\;$and $\;\displaystyle\sum_{r=0}^n(-1)^{n+r}\binom{n}{r}r^n=n!$

(as noted in WW1's answer).

---

Let $T(j,n)$ be the number of ways to distribute $j$ distinct balls into $n$ distinct boxes so that no box is empty,

so $T(j,n)=0$ if $j<n$ and $T(n,n)=n!$.

If we let S be the set of all ways to distribute the balls into the boxes, and

let $A_{i}$ be the set of distributions with box $i$ empty, for $1\le i\le n$, we have

$T(j,n)=\lvert \overline{A_1}\cap\cdots\cap \overline{A_n}\rvert=\lvert S\rvert-\sum\lvert A_i\rvert+\sum\lvert A_i\cap A_j\rvert-\sum\lvert A_i\cap A_j\cap A_k\rvert+\cdots$

$\displaystyle\hspace{.47 in}=n^j-\binom{n}{1}(n-1)^j+\binom{n}{2}(n-2)^j-\binom{n}{3}(n-3)^j+\cdots+(-1)^n\binom{n}{n}(n-n)^j$

$\displaystyle\hspace{.47 in}=\sum_{r=0}^n(-1)^{n-r}\binom{n}{n-r}r^j=(-1)^n\sum_{r=0}^n(-1)^r\binom{n}{r}r^j$.

Since $T(j,n)=0$ for $j<n$, $\;\;\displaystyle\sum_{r=0}^n(-1)^r\binom{n}{r}r^j=0$ for $j<n$;

$\hspace{1.6 in}$and $\displaystyle\sum_{r=0}^n(-1)^{n+r}\binom{n}{r}r^n=T(n,n)=n!$

Answer 2

using the nested sums the general case can be reduced to the $k=0$ case with an interesting modification ...

$$ \begin{align} &\sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \\ \\=&\sum_{r=0}^{n} { \binom{n}{r} (-1)^r \sum_{i=0}^{n} { \binom{n}{i} k^i(-r)^{n-i} }}\\ \\=&\sum_{i=0}^{n} {\binom{n}{i} k^i \sum_{r=0}^{n} { \binom{n}{r} (-1)^r (-r)^{n-i} }} \end{align}$$

for this result to be an identity in $k$, the second sum must vanish unless $i=0$

So the theorem can be proved by proving that

$$ \sum_{r=0}^{n} { \binom{n}{r} (-1)^r (-r)^{n-i} }$$

vanishes if $1 \le i \le n$ and is equal to $n!$ if $i=0$