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

2. What if the steps are not unit steps?

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!

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"."

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:

[JNCressey]

It's funny when someone gives you a challenge sequence that they intended to have some other pattern, and you just interpolate a polynomial to it.

[michael-gary-scott]

I was taught this in high school without realising how under-the-radar it is! whenever I see a non linear sequence, I immediately look at the differences. glad to see word being spread!

[jadbridge]

I was an actuarial student in the early 1970s. Part of the studies was a semester long subject called Finite Differences which covered this topic in great detail. I have used the processes many times, but this is the first time I have seen anything of it on YouTube. Thank you very much for the trip down memory lane.

[TasnuArakun]

This was the final exercise on our discrete mathematics test twenty years ago. My solution was to described the pentagonal numbers as a nonhomogeneous recurrence relation which I then solved using the characteristic equation (assuming a second degree polynomial because of the second differences all equalling 3). Apparently, this was unusual because someone wrote "wow!" in the margin.

[AshishB]

I was "taught" this in 5th grade (New York public school), where the teacher simply asked us to determine the formula for pentagonal numbers. We did it. Best math teacher ever. HERE'S THE KEY: He didn't tell us it was a tough problem.

[darkmagician]

I think like many others I've never heard anyone talk about this, but I feel slightly proud that I figured this method out myself during job interviews that had those find the pattern style questions

[lezhilo]

This looks suspiciously like a discretised version of a Taylor series. Taking one order of difference is like taking a derivative. And just like how the n-th derivative of a degree n polynomial is a constant, the n-th order difference of a degree n polynomial is also constant. In fact it seems that differentiating a polynomial and taking the difference between two values work in exactly the same way, same expanding the bracket, same cancellations, except in differentiation, you take the limit afterwards.

[Gunbudder]

that's crazy, i've never seen this before despite doing a ton of stuff with sequences in school. pretty dang useful

[christopherlee]

His videos look exact the same as a decade ago, love it.

[maxpeeters]

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"._

[antontimeboy]

another very good trick for finding out the formula for a series of integers: searching for it in the on-line encyclopedia of integer sequences 👍

[theludvigmaxis]

Us engineers use this quite often. It is used in simulation software for solid mechanics and fluid mechanics.

[hauslerful]

Mathologer also did a video about this some time ago, very glad that this gets some more screen time.

[deviatefishy]

That sure was a lot of words and also some numbers. I'm just glad to be part of the team, really.

[jakebrusca]

As a numerical analyst, I'm glad to see this material being covered more by the edutainment community on YouTube! This same idea can be used to find approximate solutions to partial differential equations! A finite difference of order N gives you an exact derivative of polynomials up to order N (this can be seen through Taylor remainders theorem), and so you use this technique to find polynomial or piecewise polynomial (splines) approximations of the solution to a PDE.

[lenskihe]

Mathologer made a brilliant video on this

[freeshavaacadooo]

This is like taking a discrete derivative and then integrating at every step back to get the original function. Neat trick.

[eamonnsiocain]

Excellent! Your explanations are always clear.

[samisadik]

Love you man! Make more of these videos, really helpful and useful too.

[JesusP]

I knew the name and even used this some times, but i had no idea of the intuition and the general formula! So interesting and well explained!