An identity for the factorial function

The top rows are indeed made of the powers $i^n=P_n(i)$, which are polynomials of degree $n$, with the leading coefficient $1$.

On the next row you take the first order difference. By the binomial formula, we have

$$P_{n-1}(i)=P_n(i+1)-P_n(i)=i^n+ni^{n-1}+\cdots-i^n=ni^{n-1}+\cdots$$

which is a polynomial of degree $n-1$ with the leading coefficient $n$.

For the next row, $$P_{n-2}(i)=P_{n-1}(i+1)-P_{n-1}(i)=n(n-1)i^{n-2}+\cdots$$ and so on.

On the last row, we have a polynomial of degree $0$ with the leading coefficient $n!$, and all the rest has vanished.


Actually you will make the same observation starting with any polynomial in $i$: the final value is $p_nn!$, where $p_n$ is the initial leading coefficient. And if you enlarge the table to the right, the bottom row remains constant.

E.g.

$$2i^3+i\\\Delta_1=6i^2+6i+3\to2\cdot3\,i^2\\\Delta_2=12i+4\to2\cdot3\cdot2\,i^1\\\Delta_3=12\to2\cdot3\cdot2\cdot1\,i^0.$$


Here is another way to show that $$ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n = n!$$

We consider the set $S$ consisting of all strings of length $n$ consisting of the symbols $a_1, a_2, \cdots, a_n$, with repetition allowed.

Then we clearly have that $|S|=n^n$ because there are $n$ choices for each symbol in the string.

Now let $A_k$ be the set of all such strings which does not contain the symbol $a_k$.

For any natural numbers $i_1, i_2, \cdots, i_k$ (where $k\leq n$ is some natural number) such that $$ 0 < i_1 < i_2 < i_3 \cdots < i_k \leq n$$ we can calculate the cardinality of the set $$ A_{i_1}\cap A_{i_2}\cap A_{i_3} \cap\cdots\cap A_{i_k} $$

There are $(n-k)$ options for each symbol in some string in the intersection above, since such a string can consist of (and can only consist of) any of the symbols which are not $a_{i_1}, a_{i_2}, \cdots, a_{i_k}$.

We thus see that $$ \left|A_{i_1}\cap A_{i_2}\cap A_{i_3} \cap\cdots\cap A_{i_k} \right| = (n-k)^n $$

We can now apply the inclusion-exclusion principle to find the cardinality of the set $$ A_1\cup A_2\cup A_3 \cup\cdots\cup A_n $$

We have that $$ \left|A_1\cup A_2\cup A_3 \cup\cdots\cup A_n \right| = \sum_{k=1}^{n} (-1)^{k+1} \left(\sum_{0<i_1<i_2<\cdots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap A_{i_3} \cap\cdots\cap A_{i_k} \right|\right) $$

For each $k$, there are $\binom{n}{k}$ ways to choose the numbers $i_1, i_2, i_3, \cdots, i_k$, and so we see that the above sum is equal to $$ \sum_{k=1}^{n} (-1)^{k+1}\binom{n}{k} (n-k)^n = \sum_{k=0}^{n-1} (-1)^{n-k+1} \binom{n}{k} k^n $$

Finally, we consider the set $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$

From our work above, we can see that its cardinality is $$\begin{gather} |S| - \left|A_1\cup A_2\cup A_3 \cup\cdots\cup A_n \right| = n^n - \sum_{k=0}^{n-1} (-1)^{n-k+1} \binom{n}{k} k^n \\ = n^n + \sum_{k=0}^{n-1} (-1)^{n-k} \binom{n}{k} k^n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n \end{gather}$$ which is the sum which we set out to evaluate. We wish to show that this is equal to $n!$.

Now any element of the set $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$ must contain all of the symbols $a_1, a_2, a_3, \cdots, a_n$, since if it did not contain $a_k$ for some $k$, then it would be an element of $A_k$, and hence of $$ A_1\cup A_2\cup A_3\cup\cdots\cup A_n $$

Conversely, any string which contains all of the symbols $a_1, a_2, a_3, \cdots, a_n$ is an element of $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$ since such a string is in $S$, but not in any of the $A_k$'s.

We see that $$ S \setminus \left(A_1\cup A_2\cup A_3\cup\cdots\cup A_n\right) $$ consists precisely of the permutations of the symbols $a_1, a_2, a_3, \cdots, a_n$ and so its cardinality is $n!$. We have thus shown that $$ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n = n!$$ as desired.


Nice observation. This comes from Newton's series applied to $f(x)=x^n$.

It is the discrete analog of $f^{(n)}(x)=n!$.