Return to MENU
Back

Activity 4 - Finite Differences and Inductive Proof

This Activity and the related Essays on the History of Mathematics are on-line at MATHGYM (http://www.mathtrak.com.au/mic/)

[-Figurate Numbers-] [-Finding the formula - Finite Differences-] [-Mathematical Induction-]

In this activity you will learn both a method for finding the equation given a table of related numbers, and for proving that the equation is correct using the technique of Mathematical Induction. To fully appreciate this Activity you need some understanding of elementary algebra.

Figurate Numbers

We believe that the Pythagoreans arranged pebbles in the shape of a regular polygons (e.g. equilateral triangle, square, pentagonal etc ). We call these numbers figurate numbers. For example:

Figurate Number	Geometric shape
triangular numbers
square numbers
pentagonal numbers

It is trivial to find the n^th term of the square numbers (the 10^th term is 10² = 100 ) but it is not so clear how to get the formula for the n^th term of the triangular numbers. There is a useful method called "finite differences" which we can use and I will try to explain how it works below for you. It is somewhat complex so bear with me as it is also pretty powerful (and nifty).

Finding the formulas - Finite Differences

We start by placing the data in a table. Let's use the data for the triangular numbers. Notice that the two columns contain the term number (n) and the corresponding value for the n^th term ( t_n ).

term (n)	n^th term (t_n)
1	1

2	3

3	6

4	10

We now add a third column called the "first differences". In this column we place the difference between each consecutive number in the sequence. For example the first two terms are 1 and 3 so the difference is 2 ; the next pair of terms is 3 and 6 with a difference of 3.

term (n)	n^th term (t_n)	1^st diff.
1	1
		2
2	3
		3
3	6
		4
4	10

You should stop at this stage and check the values in the "first differences" column. If they happen to be a constant ( i.e. all of them the same - 1 or 23 or something ) then the relationship between the values is linear. That is the formula is of the form y = mx+c.
The numbers in our pattern aren't constant so we go to the next step. Next we add a fourth column called the "second differences". In this column we place the difference between each consecutive number in the "first differences" column. For example the first two values are 2 and 3 so the difference is 1 ; the next pair of values are 3 and 4 with a difference of 1 also.

term (n)	n^th term (t_n)	1^st diff.	2^nd diff.
1	1
		2
2	3		1
		3
3	6		1
		4
4	10

By now you have noticed that all the values in the "second differences" column are a constant ( 1 ). Whenever this happens we know that the relationship is quadratic . That is the formula is of the form
y = ax²+bx+c .
It only remains for us to find the quadratic equation. We do this by extending the table in the following way:

1. First of all we add another column which contains some multiple of t_n. Which multiple of t_n we put in this column depends on the constant in the "second differences" column. If the constant is 2 we simply repeat each value in the t_n column. If the constant isn't 2, we work out what we have to multiply the constant by to get the value of 2. In our example, the constant in the "second differences" column is 1 so we have to multiply by 2. So in our new column we put 2 times each of the values in the t_n column. This is shown below:

term (n)	n^th term (t_n)	1^st diff.	2^nd diff.	2t_n
1	1			2
		2
2	3		1	6
		3
3	6		1	12
		4
4	10			20

2. Next we add another column which is the result of the difference between that last column ( in this case 2t_n ) and n²:

term (n)	n^th term (t_n)	1^st diff.	2^nd diff.	2t_n	2t_n - n²
1	1			2	1
		2
2	3		1	6	2
		3
3	6		1	12	3
		4
4	10			20	4

3. At this stage we would do our differences again to find the linear equation equal to 2t_n - n². But with this example we can see that the values in the 2t_n - n² column are identical to the values in the (n) column. This means that:
2t_n - n²= n
<=> 2t_n = n² + n
<=> t_n = ( n² + n )/2
And this is the formula for the n^th term of the triangular numbers!

For your interest, if it takes three differences to get a constant than the relationship is a cubic of the form:
y = ax³ + bx² + cx + d. If the constant is equal to 6 the value of t_n is unchanged. You continue to use the process above to find the equation.

Question 1:

See if you can find the equation for finding the n^th term in the pentagonal numbers.

Question 1 - Answer

Mathematical Induction
The formulas above seem to work in every case we try. But how can we be sure, that is prove, that they are correct?
In a previous essay we investigated the discovery made by the early Pythagoreans about the relationship between the gnomon and the square numbers. This relationship can be viewed in another form - the sum of consecutive odd numbers:

1 = 1
1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25
1 + 3 + 5 + 7 + 9 + 11 = 36

A clear pattern emerges in the sums 1, 4, 9, 16, 25, 36; they are the squares of the natural numbers l, 2, 3, 4, 5, 6. We can generalise our observation by making the conjecture: "The sum of the first n odd positive integers is equal to n², or, stated in symbols,

1 + 3 + 5 + 7 + ...+ (2n-1) = n²

Let us be clear about this way of writing a general equation. The n^th odd number can be written generally as 2n-1. The "+...+" means "continue this pattern". So this equation reads "the sum of the first n consecutive odd numbers is n squared"

Is the pattern a proof of our conjecture? No it isn't. We have already established that a few correct examples doesn't prove a general formula, because the next example we try might be a contradiction. Perhaps the easiest way to prove that a general formula of the type above is valid for every positive integer n, is to use mathematical induction.

The Principle of Mathematical Induction

To explain the principle behind mathematical induction I like to think of a row of dominos all standing on their ends

and all placed close enough so that if one domino falls, all will fall (if you have any dominos around you should try this - it's fun).

How can we prove the conjecture: "For any equally spaced row of dominos, the last domino will fall if the first one is pushed over"? Let us start by putting two dominos up, then three, then four, etc. and test them to see if they all fall. We start with the simplest case - that of two dominos. If the distance between them is correct, both will topple. We will call this case D₁.

Next we look at the second case (of three dominos), D₂:

Once again, if the distances are the same as in D₁ then the third domino will fall. We continue like this testing each of the third case D₃, the fourth D₄, and so on. Since I don't know how many dominos there are in total I will call the last case, where there are n+1 dominos that fall the D_n ^th case.

If we are to prove the general case then we have to test for every case. Let us start with the first five cases (D₁,D₂,D₃,D₄,D₅). We can test these by physical trial and find that these work if they are set up properly. The conjecture actually comprises the infinitely many cases " D₁ will fall, D₂ will fall, D₃ will fall,..." . So far, we have seen only that D₁,D₂,D₃,D₄,D₅ fall and we want to establish that all of (infinitely many) of these cases will fall before we actually test them.

The principle of mathematical induction states that we can establish the truth of any such infinite sequence of cases if we can prove two results:

that D₁ works;

that D_k+1 follows from D_k for every positive integer k.

The idea is that if we can prove that "if the first domino makes the second domino fall (D₁ works), and that any domino that falls (D_k) will knock over the next one (D_k+1)" , then we can conclude:
D₁ works
D₁ will cause D₂,
D₂ will cause D₃,
D₃ will cause D₄,
D₄ will cause D₅,
and so on.

So if we prove 1 we will have a start on this chain, and the case of D₁,D ₂, D₃, D₄, and so on, will follow on from the case of D₁ by 2.

Testing that D₁ works
All we need do is set up the two dominos at the correct separation and push the first one over. If the second falls then know that D₁ works.
Testing that D_k+1 follows from D_k for every positive integer k.
The key to whether all the dominos fall is in the separation between each domino. If the separation between any pair of dominos is the same as the separation in D₁, then any falling domino will strike the next domino in line which should also fall. Let us assume that somewhere in the row a domino is falling and that this "falling domino" is the last domino in case D_k. Since D_k works then the last domino of D_k will fall against the next domino in line which will also fall. This is case D_k+1 which works because D_k works. So we have established that D₁ is true, and that if one of the cases is true so is the next one which means that D₂ is true. But this means that D₃ is true ..., which means that D_n is true. Which proves, by induction that all the dominos will fall.

Now let us return to the conjecture: "The sum of the first n odd positive integers is equal to n²"
Let us call P_n = 1 + 3 + 5 + 7 + ...+ (2n-1) = n² so that:
P₁ =1 = 1
P₂ =1 + 3 = 4
P₃ =1 + 3 + 5 = 9
P₄ =1 + 3 + 5 + 7 = 16
P₅ =1 + 3 + 5 + 7 + 9 = 25
P₆ =1 + 3 + 5 + 7 + 9 + 11 = 36

We can tell by actual calculation that all six statements are true. The conjecture "P_n is true for every positive integer n" actually comprises the infinitely many assertions "P₁ is true, P₂ is true, P₃ is true,..." . So far, we have seen only that P₁, P₂, P₃, P₄, P₅, P₆ are true and we want to establish the truth of all (infinitely many) of these cases. Here is how we use Induction:

Testing that P₁ works
This is not difficult since P₁ is simply 1 = 1.
Testing that P_k+1 follows from P_k for every positive integer k.
If the conjecture is true then
P_k = 1 + 3 + 5 + 7 +...+ (2k-1) = k²
and
P_k+1 = 1 + 3 + 5 + 7 +...+ (2k+1) = (k+1)²
What we have to do is, starting with P_k show that P_k+1 follows as a consequence.
To get P_k+1 from P_k, we have to add on the next odd number after (2k-1), so let us add (2k+1) to both sides of the equation P_k:
P_k + (2k+1) = 1 + 3 + 5 + 7 +...+ (2k-1) + (2k+1) = k² + (2k+1)
    = k² + 2k + 1
    = (k+1)²
    = P_k+1

Thus P_k+1 follows from P_k. We have established that if any one of the cases ( P_k) is true so is the next one (P_k+1). We also proved that P₁ is true, which means that P₂ is true. But this means that P₃ is true ... , which means that P_n is true, which is the proof of our conjecture by mathematical induction.

Question 2:

See if you can prove the Conjecture - 1 + 2 + 3 + 4 + ... + n = (n²+n)/2 by mathematical induction. This is also the formula for the n^th term of the triangular numbers.

Question 2 - Answer

Question 3:

See if you can prove the Conjecture - 1 + 4 + 7 +...+ (3n-2) = (3n²-n)/2 by mathematical induction. This is also the formula for the n^th term of the pentagonal numbers.

Question 3 - Answer

Answer Question 1

term (n)	n^th term (t_n)	1^st diff.	2^nd diff.	(2/3)t_n	(2/3)t_n - n²
1	1			2/3	-1/3
		4
2	5		3	10/3	-2/3
		7
3	12		3	8	-1
		10
4	22		3	44/3	-4/3

From the table we can see that the values in the column (2/3)t_n - n² are identical to negative one third times the values in the (n) column. This means that:
(2/3)t_n - n²= (-1/3)n
<=> 2t_n - 3n² = -n
<=> t_n = (3n² - n )/2
And this is the formula we wanted to find!

Back

Answer Question 2

Let P_n = 1 + 2 + 3 + 4 + ... + n = (n²+n)/2

Testing that P₁ works
This is not difficult since P₁ is simply 1 = 1.

Testing that P_k+1 follows from P_k for every positive integer k.
If the conjecture is true then
P_k = 1 + 2 + 3 + 4 + ... + k = (k²+k)/2
and
P_k+1 = 1 + 2 + 3 + 4 + ... + k+1 = ((k+1)²+(k+1))/2 = (k²+3k+2)/2
What we have to do is, starting with P_k show that P_k+1 follows as a consequence.
To get P_k+1 from P_k, we have to add on the next number after k, so let us add (k+1) to both sides of the equation for P_k:

P_k + (k+1) = 1 + 2 + 3 + 4 +...+ k + (k+1)    = (k²+k)/2 + (k+1)
    = (k²+k+2k+2)/2
    = (k²+3k+2)/2
    = P_k+1

Thus P_k+1 follows from P_k. We have established that if any one of the cases ( P_k) is true so is the next one (P_k+1). We also proved that P₁ is true, which means that P₂ is true. But this means that P₃ is true ... , which means that P_n is true, which is the proof of our conjecture by mathematical induction.

Back

Answer Question 3

Let P_n = 1 + 4 + 7 + 10 + ... + (3n-2) = (3n²-n)/2

Testing that P₁ works
This is not difficult since P₁ is simply 1 = 1.

Testing that P_k+1 follows from P_k for every positive integer k.
If the conjecture is true then
P_k = 1 + 4 + 7 + 10 + ... + (3k-2) = (3k²-k)/2
and
P_k+1 = 1 + 4 + 7 + 10 + ... + (3k+1) = (3(k+1)²-(k+1))/2 = (3k²+5k+2)/2
What we have to do is, starting with P_k show that P_k+1 follows as a consequence.
To get P_k+1 from P_k, we have to add on the next number after 3k-2, so let us add (3k+1) to both sides of the equation for P_k:

P_k + (3k+1) = 1 + 4 +...+ (3k-2) + (3k+1) = (3k²-k)/2 + (3k+1)
    = (3k²-k+6k+2)/2
    = (3k²+5k+2)/2
    = P_k+1

Back