So how would you go about doing this "
Lagrange interpolation" by hand on a
quiz?
Well, suppose we're given a sequence 2,5,10,17. We'll write down the numbers in one row, then below them their differences, and then proceed writing successive differences:
2 5 10 17 ? ...
3 5 7 ?
2 2 ?
Eventually we get a
constant row
(note that each row is one number shorter, so obviously we might get a length=1 row, which is constant; this probably doesn't count as a "solution").
Now extend the table: the constant row remains constant, the other entries are then forced:
2 5 10 17 26 37 ...
3 5 7 9 11 ...
2 2 2 2 ...
Note that, amazingly enough, the
method of successive differences has found the numbers of the sequence
n2+1.
This method works for any polynomial sequence.
If, instead of differences, we also allow ourselves to pick quotients, we can "discover" rules for a wider class of sequences (of course, since every row is still shorter, we can now discover more rules for any given sequence fragment...). For instance, the sequence 1,2,4,8,16,32,... is probably best "explained" by taking a quotient at the first step, and getting a constant row of 2's.
The extended method can additionally find any sequence that is polynomial in n and an, for any constant a. But nn, for instance, is still beyond the scope of this method.