Why does this process generate the factorial of the exponent?

Question

Consider the process of taking a series of numbers and constructing a new series consisting of the difference between consecutive terms, and repeating this until a constant is reached:

$$2,8,18,32,50\\6,10,14,18\\4,4,4$$

When this process is applied to sequences of the form $f(n) = n^a$, the constant reached seems to always be $a!$:

$$1,2,3\\1,1$$

$$1,4,9,16\\3,5,7\\2,2\\$$

$$1,8,27,64,125\\7,19,37,61\\12,18,24\\6,6$$

$$1,16,81,256,625,1296\\15,65,175,369,671\\50,110,194,302\\60,84,108\\24,24$$

Can it be proven?

Answer 1

Yes, it always yields the factorial.

The way you describe to construct each new sub-series from the one above it is similar to taking the derivative of a power function, but at discrete intervals. The rule for taking the derivative of a power function is that $\frac{d}{dx}x^a=ax^{a-1}$. Repeatedly taking this derivative until there is a constant (the power is 0) means that the final coefficient in $cx^0$ will be $a(a-1)(a-2)\dots(2)(1)$, or $a!$.

Answer 2

Yes it has a very beautiful proof.

I highly recommend to read about Stirling numbers of second kind...

Actually it is equal to the number of coloring of $n$ balls with $n$ color in such a way that every color used.

By double counting it will be equal to a sequence which arise from include-exclude principle...

I prefer to not go to details because it would be charming to you to do it by yourself.

As a reference I remember a very nice article name "Close encounters with the Stirling number of second kind" By Boyadzhiev You can find the proof and some fascinating generalization

Answer 3

Observe that when taking iterated backward differences of a sequence $Q(k)$ we obtain $Q(k)-Q(k-1),$ $Q(k)-2Q(k-1)+Q(k-2)$ and so on, hence we have by induction that the $a$th backward difference is given by

$$\sum_{m=0}^a {a\choose m} (-1)^m Q(k-m).$$

Now with $Q(k) = k^a$ this becomes

$$\sum_{m=0}^a {a\choose m} (-1)^k (k-m)^a.$$

This sum has appeared quite frequently on MSE and may be evaluated by putting

$$(k-m)^a = \frac{a!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} \exp((k-m)z) \; dz.$$

We get for the sum

$$\frac{a!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} \sum_{m=0}^a {a\choose m} (-1)^m \exp((k-m)z) \; dz \\ = \frac{a!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{a+1}} \exp(kz) (1-\exp(-z))^a \; dz.$$

This is $$a! [z^a] \exp(kz) (1-\exp(-z))^a$$ but

$$1-\exp(-z) = z - \frac{z^2}{2} + \frac{z^3}{6} - \cdots$$

and we obtain $a!\times 1 = a!$ as claimed since the power in $a$ starts at $z^a$.

Answer 4

Denote $D$ to mean the operation mapping $f(x)$ to $f(x+1)$. And denote $I$ to mean the operation mapping $f(x)$ to $f(x)$.

You are interested in,

$$(D-I)^n x^n$$

$D,I$ are linear operators so we are allowed to treat $(D-I)^n$ as a polynomial. By binomial theorem, we have:

$$(D-k)^n x^n=\left(\sum_{k=0}^{n} (-1)^{n-k}{n \choose k}I^{n-k}D^{k} \right) x^n$$

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

Because we have $(D-i)^n x^n$ is constant, an easy proof using binomial theorem (below), we can choose and $x$ so long as $x \in \{0,1,2,.....\}$. Choose $x=0$. Then we get,

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

$$=k!S(n,n)$$

Where $S$ denotes the Stirling numbers of the second kind.

$$=k!$$

Here is the proof that $(D-I)^n x^n$ is constant.

$$(D-I)x^n=(x+1)^{n}-x^{n}={n \choose 0}x^n+{n \choose 1} x^{n-1}1^1+...-x^n=nx^{n-1}+...$$

So,

$$(D-I)x^{n-1}=(n-1)x^{n-2}+...$$

And for $s$ an integer where $s<n$.

$$(D-I)x^{n-s}=(n-s)x^{n-s-1}+...$$

Also for a constant $c$,

$$(D-I)(c)=0$$

Because $(D-I)$ is a linear operator we can combine the results above and see it that $(D-I)$ maps a polynomial of degree $n$ to a polynomial of degree $n-1$.