An identity for the factorial function

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

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

Answer 4

If I have well understood, you want the closed form of the sum

$$S_n=\sum_{k=0}^{n}(-1)^{n-k}{n\choose k} k^n$$

We start from $$(1-x)^n=\sum_{k=0}^n (-1)^{k} {n \choose k} x^k$$ We replace $x$ by $\exp(t)$:

$$(\exp(t)-1)^n=\sum_{k=0}^n (-1)^{n-k}{n \choose k}\exp(kt)$$ and we differentiatble $n$ time with respect to $t$, and we put $t=0$.

As $\displaystyle (\exp(t)-1)^n=t^n+t^{n+1}g_1(t)$ for some serie $g_1(t)$, we get $\displaystyle (\frac{d}{dt})^n((\exp(t)-1)^n)=n!+tg_2(t)$, and putting $t=0$, we get $n!$. Now $$(\frac{d}{dt})^n(\sum_{k=0}^n (-1)^{n-k}{n \choose k}\exp(kt))=\sum_{k=0}^n (-1)^{n-k}{n \choose k}k^n\exp(kt)$$ and replacing $t$ by $0$ gives the formula.

Answer 5

The Right Answer to this is certainly Yves Daoust's, but here is another combinatorial proof that I think is easier than Dylan's.

So, by way of reminder, we are trying to show that $\sum_k(-1)^{n-k}\binom{n}{k}k^n=n!$. So, interpreting the left-hand side as simple-mindedly as possible, consider configurations of the following sort: we have a list of $n$ positive integers, some of which (call the number $k$) are written in black and the others in red, and they're all at most $k$. We claim that there are $n!$ more such configurations with an even number of red dots than with an odd number of red dots.

That "at most $k$" condition is suggestive. Instead of using numbers, let's use something else we have $k$ of: the black things in our list. So now our configuration looks like this. We have $n$ dots in a row, coloured red or black. There is an arrow from each dot to another dot, and that other dot is always a black one. And we claim there are $n!$ more such configurations with an even than with an odd number of red dots.

There's a fairly natural set of $n!$ configurations with an even number of red dots, namely the ones where all the arrows have different targets. (In which case, every dot is the target of some arrow and therefore there are no red dots.) So perhaps we can pair off all the others so that the configurations in each pair have different "red parity"?

Yes, we can. Pick any configuration of arrows (never mind the colouring) in which some dot isn't the target of any arrow. Take, in fact, the leftmost such dot. Pair each configuration with the one obtained by just changing the colour of that dot. Done.

(I think there is a sense in which this is equivalent to Dylan's proof, actually, but I think it's easier this way.)

Answer 6

Here is how I like to look at this formula.

Take any function (regular enough) $f$. You have the equality $f(x+1)-f(x) = \int_x^{x+1} f'(y) dy$. Note $g(x)$ this function. Then we have: $$ g(x+1)-g(x) = \int_x^{x+1} g'(y)dy = \int_x^{x+1} f'(y+1)-f'(y) dy$$ Applying our formula once again we get: $$f(x+2) -2 f(x+1)+f(x) = g(x+1)-g(x) = \int_x^{x+1} \int_y^{y+1} f''(z) dz dy.$$

Using a nice induction one can prove (for any regular enough $f$): $$ \sum_{k=0}^{n} (-1)^{n-k}\binom{k}{n} f(x_1+k) = \int_{x_1}^{x_1+1} \cdots \int_{x_n}^{x_n+1} f^{(n)}(x_{n+1}) dx_{n+1} \ldots dx_2. $$

Now if you take $f=P$, a polynomial of degree $n$, its $n$-derivative is constant, and equal to $p_nn!$, where $p_n$ is the initial leading coefficient. By integration, the whole right hand side of our equality is $p_nn!$, and in the end you get the formula from Yves Daoust's answer:

$$ \sum_{k=0}^{n} (-1)^{n-k}\binom{k}{n} P(x+k) = p_nn! $$

Answer 7

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.

Answer 8

Let's say we want to prove that iterating $n^3$ three times gives us $3!$. (Assume we already know that your thing works for $n^2$, $n$, and $1$.)

Well, if you iterate $n^3$ once, you get $(n+1)^3-n^3=3n^2+3n+1$. We also know that iterating $3n^2$ two times gives us $3\times2!=3!$, and we know that iterating $3n$ and $1$ two times both give us $0$ (since they become constant after one or zero iterations respectively).

Thus, iterating $3n^2+3n+1$ two times gives us $3!$, and therefore iterating $n^3$ three times gives us $3!$.

Can you generalize this argument?