Method of Finite Differences

Introduction

The finite difference is an interesting topic in Number Theory that has some significant applications, in particular the final proposition of Euler’s proof for Fermat’s Sum of Two Squares Theorem.

Consider the function $f(x) = x^k$. For $x \in \{1,\ 2,\ 3,\ 4,\ 5\}$ we have $f(1) = 1^k,\ \dots,\ f(5) = 5^k$. The method of finite differences suggests that taking $k$ consecutive differences will yield $k!$. In this example, $x$ has $5$ elements so there can be a total of $4$ consecutive differences as shown in table below:

Consecutive differences

The method of finite difference states that the final consecutive difference is equal to $4!$, since there were $4$ consecutive subtractions. Indeed if we use $k = 4$ in the final equation we get:

\[5^4 - 4(4^4) + 6(3^4) - 4(2^4) + 1 = 24 = 4!\]

The above example can be extended for any integer set $x \in \{1,\ 2,\ 3,\ \dots\}$, the consecutive differences will equal the factorial of the number of consecutive differences (namely the cardinality of $x$ minus $1$).

In fact, it can also be shown that for $k$ not equal to the maximum number of consecutive differences, that the $k^{th}$ difference is still $k!$, as illustrated from the example. Take the $2^{nd}$ consecutive difference ($k = 2$) of the first $3$ terms:

\[4^k - 2(3^k) + 2^k = 4^2 - 2(3^2) + 2^2 = 2! = 2\]

Proof

The first step in proving this statement is to show that for any set of consecutive integers $(x \in \{1,\ 2,\ 3,\ \dots,\ a\})$ the $k^{th}$ consecutive difference is of the form

\[(a)^{k} - \binom{1}{k}(a - 1)^k + \binom{2}{k}(a - 2)^k - \binom{3}{k}(a - 3)^k + \dots\]

with $a$ being the greatest element in $x$ and $k$ the number of consecutive differences. This is consistent with the first example with $a = 5$ and $k = 4$.

This can be proven by induction:

Consider the $j^{th}$ term in the $i^{th}$ difference. The term can be expressed as:

\[ \text{$\tau$}_{i,\ j} = x_{i + j} - ix_{i + j - 1} + \binom{i}{2}x_{i + j - 2} - \binom{i}{3}x_{i + j - 3} + \binom{i}{3}x_{i + j - 4} - \dots \]

Take the $2^{nd}$ term in the $2^{nd}$ difference from the earlier example: $\text{$\tau$}_{2,\ 2} = x_{4} - 2(x_{3}) + \binom{2}{2}x_{2} = 4^k - 2(3^k) + 2^k$, where $x_i \ = \ i^{k}$.

Now it can be shown that the $j^{th}$ term in the $i^{th} + 1$ difference is of the same form:

\[\begin{gathered} \text{$\tau$}_{i + 1,\ j} = \text{$\tau$}_{i,\ j + 1} - \text{$\tau$}_{i,\ j}\\ = x_{i + j + 1} - ix_{i + j} + \binom{i}{2}x_{i + j - 1} - \binom{i}{3}x_{i + j - 2} + \dots \\ - \left[x_{i + j} - ix_{i + j - 1} + \binom{i}{2}x_{i + j - 2} - \binom{i}{3}x_{i + j - 3} + \dots \right]\\ = x_{i + j + 1} - (i + 1)x_{i + j} + \left[\binom{i}{2} + i)\right]x_{i + j - 1} - \left[\binom{i}{3} + \binom{i}{2}\right]x_{i + j - 2} + \left[\binom{i}{4} + \binom{i}{3}\right] - \dots \end{gathered}\]

Then using the well known identity: $\binom{i}{k} + \binom{i}{k + 1} = \binom{i + 1}{k}$, we have that:

\[\begin{gathered} \text{$\tau$}_{i + 1,\ j} = x_{i + j + 1} - (i + 1)x_{i + j} + \binom{i + 1}{2}x_{i + j - 1} - \binom{i + 1}{3}x_{i + j - 2} + \binom{i + 1}{3}x_{i + j - 3} - \dots \end{gathered}\]

which is indeed in the same form as $\text{$\tau$}_{i,\ j}$.

The next part of the proof involves showing that $k^{th}$ consecutive difference in equal to $k!$. This is guaranteed by a proof from Euler.

Assume there are $a$ integer terms in $x$, that is $x \in \{1,\ 2,\ 3,\ \dots\,\ a\}$ so $f(1) = 1^k,\ f(2) = 2^k,\ \dots,\ f(a) = (a)^k$. There are $a - 1$ consecutive differences which can be illustrated by extending the table in the example to include more terms.

Using the first part of the proof, we know that the $k^{th}$ consecutive difference is:

Equation 1 \[\begin{gathered} a^{k} - \binom{1}{k}(a - 1)^k + \binom{2}{k}(a - 2)^k - \binom{3}{k}(a - 3)^k + \dots \\ = a^{k} - k(a - 1)^k + \frac{k(k - 1)}{2!}(a - 2)^k - \frac{k(k - 1)(k - 2)}{3!}(a - 3)^k + \dots = k!, \end{gathered}\]

using the fact that the binomial coefficients have been expanded and we assume that the $k^{th}$ differences are indeed equal to $k!$. We will show again by induction that it is true. Since the method of finite differences is valid for a set of any size, consider the set $\{1,\ 2,\ \dots,\ a-1\}$. The $k^{th}$ consecutive difference would be:

Equation 2 \[(a - 1)^{k} - k(a - 2)^k + \frac{k(k - 1)}{2!}(a - 3)^k - \frac{k(k - 1)(k - 2)}{3!}(a - 4)^k + \dots = k!.\]

Subtracting Equation 1 from Equation 2 we get Equation 3:

\[a^k - (k + 1)(a - 1)^{k} + \frac{k(k + 1)}{2!}(a - 2)^k - \frac{k(k - 1)(k + 1)}{3!}(a - 3)^k - \dots = 0.\]

Multiplying Equation 3 by $a$ we get Equation 4:

\[a^{k+1} - a(k + 1)(a - 1)^{k} + \frac{k(k + 1)}{2!}a(a - 2)^k - \frac{k(k - 1)(k + 1)}{3!}a(a - 3)^k - \dots = 0.\]

If we then multiply Equation 2 by $k + 1$ we get Equation 5:

\[\begin{gathered} (k + 1)(a - 1)^{k} - k(k + 1)(a - 2)^k + \frac{k(k - 1)(k + 1)}{2!}(a - 3)^k - \\ \frac{k(k - 1)(k - 2)(k + 1)}{3!}(a - 4)^k + \dots = (k + 1)!. \end{gathered}\]

Finally, adding Equation 4 and Equation 5 we get Equation 6:

\[\begin{gathered} a^{k + 1} - (k + 1)(a - 1)(a - 1)^k + \frac{k(k + 1)}{2!}(a - 2)(a - 2)^k - \frac{k(k - 1)(k + 1)}{3!}(a - 3)(a - 3)^k + \dots \\ = a^{k + 1} - (k + 1)(a - 1)^{k + 1} + \frac{k(k + 1)}{2!}(a - 2)^{k + 1} - \frac{k(k - 1)(k + 1)}{3!}(a - 3)^{k + 1} + \dots = (k + 1)!, \end{gathered}\]

where Equation 6 is in the same form as Equation 1. We have shown by induction that using $k + 1$ instead of $k$ in Equation 1 does indeed yield the equation in Equation 6. This is also true for all cases, in particular when considering the most trivial case: the first difference of the set $x \in \{1,\ 2,\ \dots\}$. The first consecutive difference of the set is $2^1 - 1^1,\ 3^1 - 2^1,\ \dots$ with $k = 1$ (only one consecutive difference) so $2 - 1,\ 3 - 2,\ \dots = 1$ which is indeed $k! = 1! = 1$.

Thus given the sequence $1^k,\ 2^k,\ \dots,\ a^k$, the $k^{th}$ consecutive difference is equal to $k!$.