Sequences with recurring finite differences
11 Jun 2023
The finite difference operator is the discrete analogue of the derivative. It is usually written \(\Delta\) and is defined by the equation \(\Delta(f)(x) = f(x + 1) - f(x)\). That is, given a sequence \(f\), it returns a new sequence \(\Delta(f)\), called the “difference” of \(f\), whose terms are the differences between consecutive terms of \(f\).
For example, if \(f\) is the sequence of triangular numbers (0, 1, 3, 6, 10, 15, …) then \(\Delta(f)\) is the sequence (1, 2, 3, 4, 5, …), because 1 − 0 = 1, 3 − 1 = 2, 6 − 3 = 3, and so on. Applying the finite difference operator again results in the constant sequence (1, 1, 1, …). This sequence is called the “second difference” of \(f\) and is denoted \(\Delta(\Delta(f))\) or \(\Delta^2(f)\).
If we start instead with \(f(x) = x^3\), we find that the third difference, \(\Delta^3(f)\), is constantly 6:
\[\begin{array}{r|ccccccc} & 0 & 1 & 2 & 3 & 4 & 5 & \ldots \\ \hline f & 0 & 1 & 8 & 27 & 64 &125 & \ldots \\ \Delta(f) & 1 & 7 & 19 & 37 & 61 & 91 & \ldots \\ \Delta^2(f) & 6 & 12 & 18 & 24 & 30 & 36 & \ldots \\ \Delta^3(f) & 6 & 6 & 6 & 6 & 6 & 6 & \ldots \\ \end{array}\]This is reminiscent of differential calculus, where the third derivative of \(x^3\) is also constantly 6. However, the intermediate differences and derivatives do not coincide. For example, the first derivative of \(x^3\) is \(3x^2\), but you can see in the table above that the first difference of \(x^3\) begins with 1, 7, 19, …, and is in fact equal to \(3x^2 + 3x + 1\).
Other polynomials behave in a similar way. If the leading term of a polynomial \(f(x)\) is \(ax^n\), then \(\Delta^n(f)(x) = an!\), a rule whose analogue holds in differential calculus. (The \(!\) symbol here is a factorial, not a punctuation mark.) The “power rule” for finite differences is \(\Delta(x^n) = \Sigma_{i=1}^{n} \binom{n}{i} x^{n-i}\). Thus the first term of \(\Delta(x^n)\) is \(nx^{n-1}\), as with derivatives, but there are generally other terms of smaller degree.
There are other near-similarities between derivatives and differences. For example, the derivative of \(e^x\) is itself, and the difference of \(2^x\) is itself (because \(2^{x+1} - 2^x = 2^x\)). Thus \(2^x\) plays a similar role in finite difference calculus as \(e^x\) does in differential calculus.
This brings us to the main topic of this article, namely the classification of those sequences that are equal to their own \(n\)-th difference for some \(n\).
It turns out that such sequences are determined by their first \(n\) terms. That is, given a positive integer \(n\) and a list of \(n\) numbers, there is exactly one sequence which begins with that list of numbers and which is equal to its own \(n\)-th difference. One can find this sequence by “working backwards.” For example, suppose \(n = 3\), and we want the sequence to start with 0, 1, 3. The first step is to create a table, working out as many terms of the sequence’s differences, in the usual manner, as one can:
\[\begin{array}{r|ccc} f & 0 & 1 & 3 \\ \Delta(f) & 1 & 2 \\ \Delta^2(f) & 1 \\ \end{array}\]Now, since we want \(\Delta^3{f}\) to be equal to \(f\), we can add another row at the bottom with a 0 in it (the first term of \(f\)).
\[\begin{array}{r|ccc} f & 0 & 1 & 3 \\ \Delta(f) & 1 & 2 \\ \Delta^2(f) & 1 \\ \Delta^3(f) & 0 \\ \end{array}\]Just as each term in the table is the difference between the term above it and the term to its top-right (if these exist), each term is the sum of the one to its left and the one to its bottom-left (if these exist). Using this rule, we can “work backwards” to get the next term of \(f\). We find that 0 + 1 = 1, 1 + 2 = 3, and 3 + 3 = 6.
\[\begin{array}{r|ccc} f & 0 & 1 & 3 & 6 \\ \Delta(f) & 1 & 2 & 3 \\ \Delta^2(f) & 1 & 1 \\ \Delta^3(f) & 0 \\ \end{array}\]Now we can repeat the last two steps indefinitely, adding the \(i\)-th term of \(\Delta^3(f)\) at the bottom and then working upwards along a diagonal line to get the \((i+3)\)th term of \(f\).
\[\begin{equation} \begin{array}{r|ccc} f & 0 & 1 & 3 & 6 & 11 & 21 & 42 & 85 & \ldots \\ \Delta(f) & 1 & 2 & 3 & 5 & 10 & 21 & 43 & \ldots \\ \Delta^2(f) & 1 & 1 & 2 & 5 & 11 & 22 & \ldots \\ \Delta^3(f) & 0 & 1 & 3 & 6 & 11 & \ldots \\ \end{array} \end{equation}\]To find a general formula for all sequences \(f\) such that \(\Delta^3(f) = f\), we can use the same algorithm, but start with indeterminates \(a\), \(b\), \(c\) instead of 0, 1, 3.
\[\begin{equation} \begin{array}{r|ccc} f & a & b & c & 2a-3b+3c & 6a-7b+6c & 12a-12b+11c & 22a-21b+21c & 42a-41b+42c & \ldots \\ \Delta(f) & -a+b & -b+c & 2a-3b+2c & 4a-4b+3c & 6a-5b+5c & 10a-9b+10c & 20a-20b+21c \ldots \\ \Delta^2(f) & a-2b+c & 2a-2b+c & 2a-b+c & 2a-b+2c & 4a-4b+5c & 10a-11b+11c & \ldots \\ \Delta^3(f) & a & b & c & 2a-3b+3c & 6a-7b+6c & \ldots \\ \end{array} \end{equation}\]Any sequence equal to its third difference must match the table above, if you substitute \(a\) for its first term, \(b\) for its second term, and \(c\) for its third term. For example, table 2 becomes the same as table 1 if you substitute \(a = 0\), \(b = 1\), and \(c = 3\). And if you substitute \(a = -a + b\), \(b = -b + c\), and \(c = 2a - 3b + 2c\), the first row of table 2 is transformed into the second row. (This works because if \(f\) is equal to third difference, then \(\Delta(f)\) is also equal to its third difference—namely \(\Delta^4(f)\)—and so must also conform to the general case.)
The coefficients of \(a\), \(b\), and \(c\) in the general case form three separate sequences.
- Coefficients of \(a\): (1, 0, 0, 2, 6, 12, 22, 42, …)
- Coefficients of \(b\): (0, 1, 0, -3, -7, -12, -21, -41, …)
- Coefficients of \(c\): (0, 0, 1, 3, 6, 11, 21, 42, …)
These three sequences form a basis, in the linear algebraic sense, of the space of sequences equal to their third difference. (I will henceforth call this space \(E_3\).) Any sequence in \(E_3\) is a linear combination of the three sequences above, meaning that if you multiply each term in the first sequence by some number \(a\), the second sequence by some number \(b\), and the third sequence by some number \(c\), and add up corresponding terms, you can get any sequence in \(E_3\) (and you will always get a sequence in \(E_3\)).
Obviously, nothing I have done here is specific to the case \(n=3\). For all positive integers \(n\), there is an \(n\)-dimensional space \(E_n\) of sequences equal to their own \(n\)-th difference, and a general formula for all sequences in this space can be found by an algorithm analogous to the one in table 2. The sequences of coefficients produced by this algorithm form a basis of the space.
I wrote a C program to automate the algorithm, which you can find here. The program asks for a “dimension” \(n\) and a “length” \(r\), and outputs the first \(r\) terms of each of the standard basis sequences of \(E_n\).
But let’s return to the case \(n=3\). We have an algorithm that will generate a sequence in \(E_3\) given its first three terms, but we don’t have any single formula for the resulting sequence. We want an expression in terms of \(a\), \(b\), \(c\), and \(i\) that will give us the \(i\)-th term of the sequence in \(E_3\) which begins with \(a\), \(b\), \(c\). The first step to finding such a formula is to find an alternative basis of \(E_3\) consisting of three sequences that each have a simple formula. One can then write the standard-basis sequences (the sequences of coefficients listed earlier) in terms of this new basis.
The sequence in \(E_3\) starting with 0, 1, 1 repeats after six terms: (0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, …). This makes it a good candidate for inclusion in the new basis. I’ll call this sequence \(S_1\). Similarly, the sequence starting with 1, 1, 0 also repeats after six terms: (1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, …). I’ll call this \(S_2\). Clearly, \(S_1\) and \(S_2\) are just shifted versions of each other. Both have an explicit expression in terms of sine:
\[\begin{align*} S_1(i) = \frac{2}{\sqrt{3}} \sin(\frac{\pi}{3} i) && S_2(i) = \frac{2}{\sqrt{3}} \sin(\frac{\pi}{3} i + \frac{\pi}{3}) \end{align*}\]Such formulas are hardly necessary, however, and betray the simplicity of these sequences. To actually calculate the values of \(S_1\) and \(S_2\), whether on a computer or by hand, you would be better off checking the value of \(i\) mod 6 and then returning -1, 0, or 1 based on the repeating structure of the sequence. For the third element of the new basis, I will use the sequence \(2^i\), which is equal to its own first difference and so is definitely contained in \(E_3\).
The expressions for the standard-basis sequences in terms of this new basis are as follows:
\[\frac{2^i - 4 S_1(i) + 2 S_2(i)}{3}\] \[\frac{- 2^i + 4 S_1(i) + S_2(i)}{3}\] \[\frac{2^i - S_1(i) - S_2(i)}{3}\]Now remember that to find the sequence in \(E_3\) starting with \(a\), \(b\), \(c\), you can multiply the standard basis sequences by \(a\), \(b\), and \(c\) respectively and then add the corresponding terms. So the \(i\)-th term of this sequence is
\[a\left(\frac{2^i - 4 S_1(i) + 2 S_2(i)}{3}\right) + b\left(\frac{- 2^i + 4 S_1(i) + S_2(i)}{3}\right) + c\left(\frac{2^i - S_1(i) - S_2(i)}{3}\right),\]which is equal to
\[\frac{(a - b + c)2^i + (-4a + 4b - c)S_1(i) + (2a + b - c)S_2(i)}{3}.\]This is exactly the formula we were looking for. By substituting specific values in for \(a\), \(b\), and \(c\), you can get an explicit, constant-time formula for any sequence in \(E_3\), knowing only its first three terms.