Chapter 2: Behaviour of sequences under forward difference
When you first saw the sequence 1 5 14 ..., the process of taking the differences might have seemed quite arbitrary. As this approach worked for this particular sequence, the natural is whether this works generally. What happens to other sequences when you apply forward difference to them? Or what if you apply it multiple times?
You've seen at the end of the last chapter, that taking forward differences of a polynomial sequence results in another polynomial sequence (which is true in general, but you'll get to this), albeit it may be computationally quite cumbersome, especially for large polynomials. Now it's time to answer the second question - the process of applying differences to multiple times is often denoted Δk.
Problem 2.1
Let the sequence 0 1 5 14 ... be denoted a. Compute Δk(a) for all k.
The solution displays when you hover above it.
Δ(a)i = i2 as you've seen.
Δ2(a)i = 2i+1
Δ3(a)i = 2
Δk(a)i = 0 for all k>3.
Interesting. After applying the difference four times, the sequence vanished and all there is left are zeros. Is it just a coincidence? Or a general phenomenon? You might intuitively see that this shouldn't be the case for all the sequences. Somehow there shouldn't be enough degrees of freedom. But can you prove it?
Problem 2.2
Find an example of a sequence whose k-th difference is never zero.
The solution displays when you hover above it.
Perhaps the easiest way how to find such sequence is to find a nonzero sequence which does not change when you apply forward difference to it. If you find it, than its difference can never be zero. If you set a0 = 1, you find that the sequence of powers of two fulfills these constrains.
After verifying that there are sequences which never become zero, the natural follow up is which sequences do terminate? You could dive into the swamp of computations and find the answer, but it might be easier to first find sequences which behave nicely.
What does it mean to behave nicely? Firstly, it should be possible to turn it into a sequence of zeros by applying multiple forward differences. Secondly, it should be easy to compute their differences (and best of all there partial sums as well). The last example from the previous chapter does not fulfill this as it was not possible to see the solution at a glance (although it wasn't difficult to compute it).
This was not very concrete indeed. The only way how to tackle this is try to spot a pattern. Let's write the desired function with its difference into a table.
| First element | Second element | Third element | Fourth element | All other | |
|---|---|---|---|---|---|
| Forward difference | Δa0 | Δa1 | Δa2 | Δa3 | ... |
| Original sequence | a0 + Δa0 | a1 + Δa1 | a2 + Δa2 | a3 + Δa3 |
Adding a value from the bottom row to a value from the upper row gives the next number in that row. Sounds familiar? No? What if you rotate the table?
That look just like a part of Pascal's triangle! The rows in our original table play the role of the diagonals in Pascal's triangle. But you know that the k-th diagonal represents the sequence of binomial coefficients ( nk ).
Problem 2.3
Verify that for sequence ai = ( ik ), (Δa)i = ( ik-1 )
The solution displays when you hover above it.
This could be solved algebraically, where you could a few properties of binomial coefficients, but there's also a combinatorial solution. We're interested in the number of ways how to choose k elements from i+1 (later referred as the first set) elements minus the number of ways how to choose k elements from i elements (the second set). As the second set is a subset of the first set, you're looking for the number of unordered sets of size k which are a subset of the first set, but not the second. That means they all have to contain the last element from the first set. When this is satisfied the last k-1 elements can be chosen arbitrarily from the other i elements. But there are exactly ( ik-1 ) way how to choose it and the statement holds for k>0 but you can check that it holds for 0 as well and the statement is therefore true.
With this statement proven, it's easy to see that such sequence results in a sequence of zeros when differenced k+1 times. With each difference the order of binomial coefficient decreases and therefore it must eventually become negative which means it's by definition zero.
These are for sure not the only sequences which lead to zero sequences when differenced multiple times. You've seen in the first problem that the series of squares shares this property, but that is certainly not a binomial coefficient.
There are two properties of the differences which can help us to get other sequences which can be differenced to zero. First - if you multiply a sequence by a constant and take a difference of that sequence it's the same as if you took the difference and multiplied it by that same constant. Second - if you sum two sequences and take the difference it's the same as if you did it in the reversed order. These properties are not difficult to prove and you're encouraged to do so if you don't see it at the first glance.
From these properties follows that if you take any linear combination of sequences of binomial coefficient they can be reduced to zero by applying differences.
With this discovery new questions arose. Are there any other sequences that these which can be reduced to zero? And which sequences are the linear combinations of sequences of binomial coefficients? You might have guessed the answer to the second question. These should be the polynomials. But such statement requires a proof.
Problem 2.4
Prove or disprove that the linear combination of sequences of binomial coefficients are the same as the polynomials.
The solution displays when you hover above it.
This proof should have two parts. The verification that all sequences of binomial coefficients can be written as polynomials and that all the power sequences can be written as a linear combination of sequences of binomial coefficients.
The first part is quite easy. A binomial coefficient of class k is by definition a product of k polynomials of degree 1. It is therefore a polynomial of degree k.
The second part is a bit harder and could've been done using the mathematical induction once again - we can get a polynomial with degree one less if we subtract an appropriate multiple of an appropriate binomial coefficient.
However there is also prettier and perhaps more difficult to understand solution using linear algebra. If you're not familiar with it feel free to skip this.
You want to shove that two vector spaces with two different basis vectors are isomorph. That means that there should be a matrix A which transforms one basis vector to the other and vice versa. You can transform the powers into the binomial coefficients easily - the k-th binomial coefficient is a polynomial of degree k. You therefore have the matrix A for this transformation. Note that as the degree is k in the k-th row, the matrix is bottom triangular and has non zero elements on the diagonal. That means it's regular and therefore has an inverse (which is also a bottom triangular matrix). But its inverse transforms the binomial coefficients into the powers and the two vector spaces are therefore equal.
So all the polynomial sequences can be reduced to zero by taking the difference. You'll see in the next chapter that these are the only sequences with this property.
In this chapter you've seen how to easily take differences of sequences where every element is binomial coefficient of the same class. For any other polynomial it's possible to express it as a linear combination of these sequences and when the coefficient for the linear combination are found, the forward differences of any order can be computed efficiently.
If we combine it with the theorem from the end of the last chapter, we see that up to a constant factor we can compute all the partial sums of these sequences as well.