An identity for the factorial function A friend of mine was doodling with numbers arranged somewhat reminiscent of Pascal's Triangle, where the first row was $ 1^{n-1} \ \  2^{n-1} \ \cdots \ n^{n-1} $ and subsequent rows were computed by taking the difference of adjacent terms. He conjectured that the number we get at the end is $ n! $ but I've not been able to prove or disprove this. The first few computations are given below:
$$ 
    \begin{pmatrix}
    1 \\
    \end{pmatrix}
$$
$$
    \begin{pmatrix}
    1   &     & 2   \\
        & 1   &     \\
    \end{pmatrix}
$$
$$
        \begin{pmatrix}
        1   &     & 4   &     & 9   \\
            & 3   &     & 5   &     \\
            &     & 2   &     &     \\
        \end{pmatrix}
$$
$$
        \begin{pmatrix}
        1   &     & 8   &     & 27  &     & 64  \\
            & 7   &     & 19  &     & 37  &     \\
            &     & 12  &     & 18  &     &     \\
            &     &     & 6   &     &     &     \\
        \end{pmatrix}
$$
$$
\newcommand\pad[1]{\rlap{#1}\phantom{625}}
        \begin{pmatrix}
        1   &     & 16  &     & 81  &     & 256 &     & 625 \\
            & 15  &     & 65  &     & 175 &     & 369 &     \\
            &     & 50  &     & 110 &     & 194 &     &     \\
            &     &     & 60  &     & 84  &     &     &     \\
            &     &     &     & 24  &     &     &     &     \\
        \end{pmatrix}
$$
I attempted to write down the general term and tried to reduce that to the required form. The general term worked out as
$$
       \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} (i+1)^{n}.
$$
I tried applying various identities of the binomial coefficients but I'm barely making any progress. Any help would be appreciated.
Small note: If I instead start with the first row as $ 0^{n} \ \  1^{n} \ \cdots \ n^{n} $ then I still get $n!$ at the end of the computation, and the general formula in this case works out as
$$
       \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} i^{n}.
$$
In fact, we can start with any $n$ consecutive natural numbers, each raised to the $(n-1)$th power, and we still get $n!$ at the end of the computation.

Oh, here's another way to look at it that I rather like. It's specific to the particular polynomial we're working with here.
So, let $a_0(n) = n^k$ and then $a_{d+1}(n)=a_d(n)-a_d(n-1)$; this question is about $a_k$. Here's the key observation: $a_d(n)$ counts $k$-tuples of numbers from $\{1,\dots,n\}$ that include at least one of every number above $n-d$.
[EDITED to fix a stupid typo: I originally had $a_d(n)$ at the start of the previous paragraph.]
We prove this by induction. For $d=0$ it's trivial. If it's true for $d$ then:


*

*$a_{d}(n)$ is the number of $k$-tuples from $\{1,\dots,n\}$ that don't omit anything above $n-d$, and

*$a_{d}(n-1)$ is the number from $\{1,\dots,n-1\}$ that don't omit anything above $n-d$,


*

*which by renumbering equals the number from $\{1,\dots,n-d-1,n-d+1,\dots,n\}$ that don't omit anything above $n-d$,

*in other words the number from $\{1,\dots,n\}$ that don't omit anything above $n-d$ but do omit $n-d$ itself.



But then the difference (which equals $a_{d+1}(n)$ by definition) is just the number of $k$-tuples from $\{1,\dots,n\}$ that don't omit anything above $n-d$ and furthermore don't omit $n-d$, which is what we were undertaking to prove $a_{d+1}(n)$ equals.
So now we know what each successive row of that difference table equals. And when we have taken differences $k$ times, it's counting $k$-tuples of numbers from $\{1,\dots,n\}$ that include at least one of each of $k$ specified numbers, and there are plainly exactly $k!$ of those whatever $n$ is.
