The Generic Number Sequence Puzzle

Question

If you are in a hurry, you can skip the story below, there's a TL;DR near the end.

The gist is that we are going to solve every number-sequence puzzle ever^*, all in one go.
_{*: Terms and conditions may apply. May be subject to availability. Contact your local maths department for further information.}

---

Charlie, a university tutor, was having a get-together with his lot of freshmen, fortuitously nicknamed Wonder, Tootsie, and Trillian.

Unfortunately, they had 4N+1 cupcakes, so the question arose, who gets the last one.

Charlie: I don't think there's any other choice, we have to settle this the old-fashioned way.
Wonder: What, a duel? Isn't that a bit extreme?
Charlie: What? No, not a duel! A bet of course!
all around: (sighs of relief)
Charlie: I'm really good at number sequence puzzles, so here's the deal: You guys pick any fourth order polynomial, and calculate its value at any 5 points. As long as the distance between two consecutive points is always the same, I can tell you the next two numbers in the sequence. If I get them right, I get the cupcake.
Tootsie: Well, big whoopty-doo, we all know how to fit polynomials.
Charlie: Okay, but what if I do it only using addition and subtraction? No more than ten of either, too. Would that be impressive enough?
Trillian: Hey, I know this trick! You are going to combine the numbers into this one huge long string of numbers, and then claim that you are only doing one addition while you are actually doing several at the same time, aren't you?
Charlie: (looking a little offended) No, that would be cheating! I won't cheat in any way. I promise!
all around: (exchanging glances, hesitant nods gradually turn into a consensus of acceptance)
Wonder: Very well. The bet is on.
Charlie: Ok, you guys figure out the number sequence, while I go return some of that excellent cider to mother nature.

While Charlie is away, the freshmen try to decide how to choose the factors for the polynomial. They'll of course also need a starting point, and the distance between the points. (Names shortened to numbers just because.)

1: Well, I'll just jot down a couple of numbers then, we'll use those as the coefficients of the polynomial, and..
2: NOT SO FAST! How do we know you are not colluding with Charlie? We all know you have a crush on him!
1: Well, so do you, so..
3: Shut up, you two. We'll use the digits of pi.
1: ..Yeah, that's probably fair. That would only give positive coefficients though.
2: So we'll subtract 5 from each digit.
3: That should work. There's a 5 in the first digits of pi though, getting a zero in one factor might make the sequence easier to solve.
1: Well, let's use "e" then.
2: Yes, let's.

So Trillian rolls up her sleeves, and starts writing. This is what she wrote:

  [2, 7, 1, 8, 2, 8, 1] (minus 5) -> [-3, 2, -4, 3, -3, 3, -4]  

-> $\mathbf{-3x^4 + 2x^3 - 4x^2 + 3x - 3}$, First point: 3, Step: -4.

"These numbers are going to get big. Anyone have a calculator? Thanks... I really don't think Charlie can solve this. I mean, even I have to do a silly number of multiplications here.."

Point:               3,  -1,    -5,     -9,    -13,     -17,     -21
Polynomial value: -219, -15, -2243, -21495, -90795, -261599, -603795

Trillian: Ok, those got pretty huge. Even it he could somehow figure them out, it's probably going to take a good while.

Charlie returns, and is handed this list of numbers: -219, -15, -2243, -21495, -90795. He then performs ten simple subtractions, followed by eight additions (the last four he calculates in one go), and grabs the cupcake less than two minutes after his return.

The freshmen stare at the correct result incredulously, until Wonder exclaims "That's bloody brilliant!" and goes to fetch Charlie another pint of cider.

What were Charlie's calculations?

---

TLDR:

Given a sequence of five ($N+1$) numbers, of which you know that they were generated by evaluating an unknown fourth ($Nth$) order polynomial at regular intervals, how can you extrapolate the next two values using 10 ($\frac{N^2+N}{2}$) subtractions and 8 ($2N$) additions only?

---

For extra credit, can you name another Charles whose name is in the history books in big part for implementing this same method very cleverly?

For another bonus point, why did Trillian roll up her sleeves?

For super-hyper-extra points, what would have happened if Trillian had made a mistake while calculating one of the five numbers?

Answer 1

[I shan't bother spoilering this; it would basically be an entire answer composed of spoiler blocks.]

Charlie does this by drawing up a table of differences. So first he writes down the numbers he's been given, the values of a 4th-degree polynomial at equally spaced points:

-219 -15 -2243 -21495 -90975

and then he computes successive differences (4 subtractions), getting the values of a 3rd-degree polynomial at equally spaced points:

204 -2228 -19252 -69480

and again, getting the values of a 2nd-degree polynomial at equally spaced points:

-2432 -17024 -50228

and again (polynomial is linear now):

-14592 -33204

and again (now we have a constant polynomial):

-18612.

Since this polynomial is constant, we can write down its value at the next two of our equally-spaced values very straightforwardly:

-18612 -18612 -18612

and now we can proceed back upwards, adding in order to produce the numbers on the previous line that would give the differences we have here:

-14592 -33204 | -51816 -70428
-2432 -17024 -50228 | -102044 -172472
204 -2228 -19252 -69480 | -171524 -343996
-219 -15 -2243 -21495 -90975 | -262499 -606495

... where we can see that at some point I have made an error in my arithmetic, but the principle is correct :-).

(Ah, I see. I copied down 90795 as 90975. I initially thought I must have made another error, but that was because of an error in the puzzle that's now been corrected :-).)

Extra credit: Charles Babbage's Difference Engine was a device for performing this procedure.

Bonus point: Not sure, besides the trivial thing that rolling up one's sleeves before doing some kind of work is a cliche.

Super-hyper-extra: The procedure always extrapolates the unique polynomial of degree at most N with the given values. So if Trillian gets one of them wrong by an amount a, the differences between her values and the true values are a times the unique such polynomial that's 1 at the value she got wrong and 0 at the others. That's always of degree N, so the errors will grow like distance^N; there's an obvious-in-hindsight explicit expression for it (mumble product of differences) which means e.g. that the differences will tend to have some nice small factors; and of course because all we're doing is addition and subtraction the extrapolated values will still be integers. So, e.g., the errors in my extrapolation above were 900 and 2700.