Discrete calculus: is my proof about the difference of two consecutive powers correct?

Question

Theorem statement: $\displaystyle \Delta^dF_n(x) = \sum_{k=0}^{n-1} \binom{n-1}{k} \Delta^{d-1}F_{n-1-k}(x)(-1)^k$

---

Proof:

$$\begin{align} F_n(x) &= x^n =\Delta^0F(x) \\[2ex] \Delta^1F_n(x) &= x^n -(x-1)^n \\[2ex] &= x^n - \sum_{k=0}^n\binom nk x^{n-k}(-1)^k \\[2ex] &= \sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-k}(-1)^{k} \\[2ex] &=x^{n-1} -(n-1)x^{n-2} + \ldots \pm (n-1)x^2 \mp 1 \\[2ex] &= \sum_{k=0}^{n-1}\binom{n-1}{k}\Delta^0F_{n-1-k}(x)(-1)^k\end{align}$$

---

$$\begin{align}\Delta^2F_n(x) &=\Delta^1F_n(x) -\Delta^1F_n(x-1) \\[2ex] &= \sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-k}(-1)^k - \sum_{k=0}^{n-1}\binom{n-1}{k}(x-1)^{n-k}(-1)^k \\[2ex] & = x^{n-1}-(x-1)^{n-1}- (n-1)x^{n-2} - (n-1)(x-1)^{n-2} +\ldots \pm(n-1)x^2 -(n-1)(x-1)^2 \\[2ex] & = \sum_{k=0}^{n-1} \binom{n-1}{k}\Delta^1F_{n-1-k}(x)(-1)^k\end{align}$$

---

$$\begin{align} \Delta^3F_n(x) &= \Delta^2F_n(x) - \Delta^2F_n(x-1) \\[2ex] &= \sum_{k=0}^{n-1} \binom{n-1}{k}\Delta^1F_{n-1-k}(x)(-1)^k -\sum_{k=0}^{n-1} \binom{n-1}{k}\Delta^1F_{n-1-k}(x-1)(-1)^k \\[2ex] &= \sum_{k=0}^{n-1} \binom{n-1}{k} (\Delta^1F_{n-1-k}(x) - \Delta^1F_{n-1-k}(x-1))(-1)^k \\[2ex] &= \sum_{k=0}^{n-1} \binom{n-1}{k} \Delta^2F_{n-1-k}(x)(-1)^k \end{align}$$

$$\therefore \Delta^dF_n(x) = \sum_{k=0}^{n-1} \binom{n-1}{k} \Delta^{d-1}F_{n-1-k}(x)(-1)^k$$

---

Is this correct? If not, where did I go wrong?

If it is correct, what can I do with this? Where can I apply the derived identity?

I originally set out to prove that $\Delta^n F_n(x) = c \ \forall x$, but I'm not sure if I'm any closer to this now.

Answer 1

There is a mistake early on:

\begin{align*} x^n - (x - 1)^n &= x^n - \left(x^n - nx^{n-1} + \frac{n(n-1)}{2}x^{n-2} - \cdots \right) \\ &= nx^{n-1} - \frac{n(n-1)}{2}x^{n-2} + \frac{n(n-1)(n-2)}{6}x^{n-3} + \cdots \\ &= \sum_{i = 0}^{n-1} \binom{n}{i}(-1)^{n-i+1}x^i \\ \end{align*}

Whereas you said this is $x^{n-1} -(n-1)x^{n-2} + \ldots \pm (n-1)x^2 \mp 1 = (x - 1)^{n-1}$.

The easiest way to describe $\Delta^k$ of some polynomial is to write the polynomial in the basis $\{x^{\underline i} : i \ge 0\}$ where $x^{\underline i} = x(x-1)(x-2)\cdots(x-i+1)$. This is a nice basis for applying $\Delta$ since $\Delta(x^{\underline i}) = ix^{\underline{i - 1}}$.

The connection coefficients are the Stirling numbers of the second kind:

$$x^n = \sum_{k = 0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline k}.$$

However, if all you care about is the identity $\Delta^n(x^n) = n!$ then it suffices that the coefficient of $x^{\underline n}$ is $1$ and the other coefficients are just some integers.

Now you can show (by induction, formally) that $\Delta^{k}(x^{\underline i}) = i(i - 1) \dots (i - k + 1)x^{\underline{i - k}} = i^{\underline k} x^{\underline{i - k}}$ and that this is $0$ if $k > i$.

It therefore follows that

$$\Delta^{n}(x^n) = \sum_{k = 0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} \Delta^{n}(x^{\underline k}) = \begin{Bmatrix} n \\ n \end{Bmatrix} \Delta^{n}(x^{\underline n}) = n^{\underline n} x^{\underline 0} = n!.$$

Alternatively, you can prove this without the change of basis:

• $\Delta^0(x^0) = 0!, \Delta^1(x^1) = x - (x - 1) = 1!$
• Assume $\Delta^{i}(x^i) = i!$ for $i < n$
• Then $\Delta^{i + 1}(x^i) = 0$ for all $i < n$ and in particular, $\Delta^{n - 1}(x^i) = i$ except $i = n - 1$.
• Now apply $\Delta^{n-1}$ to the identity at the very top:

\begin{align*} \Delta^{n-1}(\Delta^1(x^n)) &= \Delta^{n-1}\left(nx^{n-1} - \frac{n(n-1)}{2}x^{n-2} + \frac{n(n-1)(n-2)}{6}x^{n-3} + \cdots \right) \\ &= \Delta^{n-1}(nx^{n-1}) \\ &= n\Delta^{n-1}(x^{n-1}) \\ &= n(n-1)! \end{align*}

by induction.