The Finite Difference Method

Find a polynomial with the finite difference method. Take successive differences of a sequence to find the polynomial that made it.

Let me try to anticipate some questions:

1. What if we have a sequence that doesn't start at x = 0?
There's a general form of Newton's Forward Difference Formula for a sequence that starts at x = a, with 1 unit steps. Here it is on wikipedia
https://en.wikipedia.org/wiki/Finite_difference#Newton's_series

2. What if the steps are not unit steps?
There is an even more general form of Newton's Forward Difference Formula for a sequence that starts at x = a and has equally spaced steps of size h. You can see it on wikipedia at the end of the Newton series section here https://en.wikipedia.org/wiki/Finite_difference#Newton's_series

3. The finite difference method leads to a whole branch of maths called finite difference calculus.
In finite difference calculus, the difference operator (that I called D(x)) is analogous to differentiation.
Then, Newton's Difference Formula is analogous to Taylor series, and there is a whole bunch of other formulas that are analogous to calculus. But it's all for polynomials rather than any analytic function.

4. I want more YouTube videos about the finite difference method please!
James Tanton did a great one here, very approachable description of the idea https://youtu.be/_5vU48kf7NY
And Mathologer has gone into more of the details, especially the connection to calculus, here https://youtu.be/4AuV93LOPcE

5. Are a few constants enough to know we have a polynomial?
Unfortunately, you might have something that looks like a row a constants, but it is not guarantee that the procedure has finished. The formula you end up with will fit the data you currently have.

So, if it is a mystery formula, then what you have is a good guess.

For example, we could start with a sequence for x^2: 0, 1, 4, 9, 16, ...
And the finite difference method will find the formula f(x) = x^2.

But if we want to be naughty, we could add any random number to the end of that sequence:
0, 1, 4, 9, 16, 73, ....

And now we get the formula: f(x) = x + x(x-1) + (48/120)(x)(x-1)(x-2)(x-3)(x-4) = (48x)/5 - 19x^2 + 14x^3 - 4x^4 + (2x^5)/5.
This agrees with x^2 for the first few values, and then gives the value 73.

6. Max Peeters gave the following interesting comment:
"John Conway and Richard Guy explain how this method can be further extended in their book 'The Book of Numbers'. They share 2 of them, the first works for simple exponential functions as well (such as 4^n - 3^n), and the second works for sequences where each term is a sum of previous terms (like Fibonnaci's sequence).
For anyone interested: wolfram has info on both of them, they're called "Jackson's Difference Fan" and "Quotient-Difference Table"."
https://mathworld.wolfram.com/JacksonsDifferenceFan.html
https://mathworld.wolfram.com/Quotient-DifferenceTable.html

7. I think I buried one of the most interesting things about this method, that this is how the Charles Babbage Difference Engine worked. See wikipedia for all its history, and a description of how it worked by differences (basically what I said in the video) https://en.wikipedia.org/wiki/Difference_engine#Charles_Babbage's_difference_engines

8. I like the handwritten notes style, and I like that they are imperfect. But the formula at 3:49 looks a bit blobby. It says f(x) = (D^(2)(0)/2)x^2 + (D(0) - D^(2)(0)/2)x + D^(0)(0). And that can then be rearranged to say f(x) = D^(2)(0) (x(x-1)/2) + D(0)(x) + D^(0)(0).

9. Oh and if you want to check your answer for hexagonal numbers, here it is:
https://en.wikipedia.org/wiki/Hexagonal_number

Видео The Finite Difference Method канала singingbanana