Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 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(n-1)(n-2)]/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:

1

4

10

20

35

56

«---original
sequence

3

6

10

15

21

«---first
differences (D1)

3

4

5

6

«---second
differences (D2)

1

1

1

«---third
differences (D3)

Notice that the third-differences 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 third-degree, or cubic, polynomial can be found to represent the relationship, based on the ordered pairs we have.

The next question: How do we find that polynomial representation?

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.

Here's the difference table with these general elements in the original row, followed by the subsequent differences:

a+b+c+d

8a+4b+2c+d

27a+9b+3c+d

64a+16b+4c+d

125a+25b+5c+d

216a+36b+6c+d

«---original sequence

7a+3b+c

19a+5b+c

37a+7b+c

61a+9b+c

91a+11b+c

«---first differences

12a+2b

18a+2b

24a+2b

30a+2b

«---second differences

6a

6a

6a

«---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 n-2, 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:

  1. Create the difference tables for the general linear polynomial ax+b and the general quadratic polynomial ax^2+bx+c.
  2. Create a difference table for the sequence 12, 28, 50, 78, 112, 152, . . . . What type of relationship is represented? How do you know?
  3. Calculate the first several terms (n=1,2,3,...) of the sequence represented by the polynomial 2n^3+2n^2+n. In a difference table generated from this sequence, in what row will the differences first appear constant? What is that constant difference?

Here are the first four rows of a triangular array of numbers:

1

1

4

1

4

7

1

4

7

10


Use the method of constant differences to determine an explicit representation for the row sums, based on the known data.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes