Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers 
Finite Differences 

We begin our discussion of finite differences by examining column 3 in Pascal's Triangle: 1, 4, 10, 20, 35, 56, and so on. Suppose we seek an explicit representation for this sequence. One way to do that is simply to use combination notation: C(n,3) for n at least 3. This simplifies to [n(n1)(n2)]/6. There we have an explicit representation.
Another way to search for an explicit representation is to use the method of finite differences. Let us illustrate the method.
To use the method of finite differences, generate a table that shows, in each row, the arithmetic difference between the two elements just above it in the previous row, where the first row contains the original sequence for which you seek an explicit representation.
Here are the first few rows for the sequence we grabbed from Pascal's Triangle:






«original 






«first 





«second 




«third 
Notice that the thirddifferences row is constant (i.e., all 1s). This is the signal we look for in an application of finite differences. If and when we reach a difference row that contains a constant value, we can write an explicit representation for the existing relationship, based on the data at hand. In fact, we can be more specific and say that the existing relationship is a polynomial whose order is equal to the row number of the row in which the constant difference first occurs. In our example, because the constant difference first occurred in the third row of differences, a thirddegree, or cubic, polynomial can be found to represent the relationship, based on the ordered pairs we have.
We return to a difference table, but replace the elements in the first row with more general terms. In our example, if the elements in the row of original values are generated from a cubic polynomial, they all are of the form an^3+bn^2+cn+d. We compute these values for n=1,2,3 and so on, to represent the first value in the row, the second value in the row, and so on.
When n=1, an^3+bn^2+cn+d=a+b+c+d. When n=2, an^3+bn^2+cn+d=8a+4b+2c+d. Likewise, we get 27a+9b+3c+d when n=3, 64a+16b+4c+d when n=4, 125a+25b+5c+d when n=5, and 216a+36b+6c+d when n=6.






«original sequence 






«first differences 





«second differences 




«third differences 
As expected, we see a constant difference in the third row of differences. How does that help us? Compare this to the last row of our first table, where the constant differences were all 1. Setting the two rows equal to each other, we have 6a=1, or a = 1/6. This shows us that in the cubic polynomial we seek, of the form an^3+bn^2+cn+d, we know that a=1/6.
Continuing back up the tables, and knowing that a=1/6, we can write the equation 12(1/6)+2b=3, or b=1/2. Equating the first row of differences in each table, and knowing that a=1/6 and b=1/2, we can write the equation 7(1/6)+3(1/2)+c=3, showing that c=1/3. We can then determine from a+b+c+d=1 and a=1/6, b=1/2, c=1/3 that d=0.
Putting all this together into the general cubic an^3+bn^2+cn+d, we determine that 1/6n^3+1/2n^2+1/3n, or, equivalently, (1/6)(n^3+3n^2+2n)=(1/6)(n)(n+1)(n+2). Now test this. For n=1, we get 1; for n2, the expression simplifies to 4; when n=3, we get 10. These are just the first three values of the original sequence, as expected.
Here are some related problems for you to complete:
Here are the first four rows of a triangular array of numbers:
1 

1 
4 

1 
4 
7 

1 
4 
7 
10 





