next up previous
Next: Exponentials Up: Guessing Formulas Previous: Some More Examples

Finite Differences

Suppose you are asked to find a function f(x) such that

displaymath564

We might guess that the function is a polynomial of degree 3. How can we determine the coefficients?

displaymath565

In our example, tex2html_wrap_inline638 , tex2html_wrap_inline640 , tex2html_wrap_inline642 , and tex2html_wrap_inline644 so tex2html_wrap_inline646 .

In general, if you think f(x) is a polynomial of degree m, tex2html_wrap_inline652 , then

displaymath566

so

displaymath567

What is the number of different triangles you can form on a flat surface using three toothpicks for the three sides of each triangle, given an unlimited supply of toothpicks of n different colors?

displaymath568

We want a formula f(n) so that

displaymath569

Look for a pattern by subtracting these numbers from each other, making a difference table:

displaymath570

Consider some known formulas:

displaymath571

displaymath572

This suggests that for our problem we seek a formula of degree 3.

Let's call the numbers in the first row

displaymath573

and the numbers in the second row

displaymath574

and the numbers in the third row

displaymath575

etc. These aren't equal to derivatives in the sense of differential calculus, but there seems to be a strong analogy.

displaymath576

In differential calculus, we exploited;

displaymath577

What is the analog for differences? Define

displaymath578

This is sometimes called a falling factorial.

displaymath579

Verification:

displaymath580

Now we can guess formulas:

displaymath581

In our example,

displaymath582

displaymath583

Now we have a formula that we can try to prove, e.g., by induction, or directly.

In general, fetch f(0), f'(0), f''(0), ..., tex2html_wrap_inline666 as the first entries of the rows of the difference table (assuming we have reached a row of zeroes). Then

displaymath584

displaymath585

Note that

displaymath586

so

displaymath587

(taking tex2html_wrap_inline668 if n<j).

In our example,

displaymath588

Here is another way of doing the same thing--via ``antiderivatives.''

displaymath589

displaymath590

displaymath591

displaymath592

displaymath593

displaymath594

displaymath595

displaymath596

displaymath597

displaymath598

and you can verify that this is equal to tex2html_wrap_inline672 , which is the formula we had found before.


next up previous
Next: Exponentials Up: Guessing Formulas Previous: Some More Examples

Carl Lee
Wed Jan 6 11:37:02 EST 1999