EV. What’s the Difference?

Isaac Newton gave an elegant solution to this problem. Can you?

To understand the question, first consider the square numbers:

1 4 9 16 25 36 49 ….

Below successive squares, write the differences between them. For example, 4 – 1 = 3.

```1   4   9   16   25   36   49 ....

3   5   7    9     11    13 ....```

And then repeat:

```1   4   9   16   25   36   49 ....

3   5   7    9     11    13 ....

2   2   2     2      2  ....```

It turns out that for any polynomial p, if we make a table of the values p(1), p(2), etc and take differences, successively, eventually we will have a constant row, and the number of differences we need is exactly the degree of the polynomial. For example, for 2n^3 – n, we have

``` 1     14      51    124    245  .....

13   37   73   121 ....

24   36   48  ....

12   12 ...```

(and all 12’s on this row)

Now for the puzzle!

(A warm up might be to prove the assertion above, that this works at all)

If we have just the front column of the table, we can recover the rest, and in particular, the values on the top row:

```2

1

7 ```

Can only be

```
2      3    11    26    48    77 ....

1      8     15     22  29  ....

7       7      7     7    7  ...
```

It’s not too hard to figure out the polynomial that generates the values on the top row…

But more generally, give a simple formula for any polynomial in terms of the values in the first column in any such table!

(BIG WORD OF CAUTION: An elegant formula isn’t necessarily in the fully-multiplied-out form!)

1. tricycle said,

December 23, 2008 at 12:49 am

There is a typo  in reconstructing the values in the first row. They should be 2,3,11,26,48,. . .  (It looks like someone added 1+8 instead of 1+2).
The polynomial is quadratic and can then easily be found by using the column before 2,1,7, namely 8,-6, 7. The polynomial is 8 C(n,0) -6 C(n,1) +7 C(n,2) = 8 – 19n/2 +7n^2/2. Alternatively use 2,1,7 and replace n with n-1.

2. eab said,

December 26, 2008 at 11:09 pm

I’m unclear on how this works . . . (9-2) is 7, not 1.  If we take the differences from the first series, we don’t get 1.  If given 2, 1 and 7 as a column, I can see how we generate  8,15 etc. but when we go up the next row, I see the 9, 17, etc but if we’re given the 2 and the 1, I don’t see how we can solve it.  What am I missing?  Thanks.

3. eab said,

December 27, 2008 at 9:29 am

Hmm . . . I guess my glasses were dirty last night when I looked at this since the numbers are 2, 3, 11 and not 2, 9 . . . Please disregard earlier comment.  I got it.

4. strauss said,

December 28, 2008 at 6:04 pm

Hi, eab and tricycle are perfectly correct! eab’s first comment prompted me to fix the typo– his glasses are fine!!

5. prunthaban said,

December 30, 2008 at 1:58 am

An attempted solution,
This looks like a discrete version of Mclaurin series…
The result looks like, f(x) = a1 + C(x,1)*a2 + C(x, 2) * a3…..C(x,n-1) * an

Here C(n,c) is the binomial coefficient. a1, a2… an are the given numbers in the first column.

Technically speaking in my formula f(0) will be the first term and not f(1). I hope that does not matter. Otherwise I just need to use (x-1) in place of x and will make the formula ugly. By the way, is there are better simplification than this? Not sure.