Friday, June 8, 2018

More connections

I've been thinking alot about polynomial deltas recently. See:  It turns out, that there are a variety of problems where its fun to use them. Basically anywhere you think you have a polynomial function and you can curve fit is a good candidate.

For example:  Find a formula for \( \sqrt{n\cdot (n+1) \cdot (n + 2) \cdot (n+3) + 1} \)

You could do the algebra and factor cleverly or you could calculate the easy values around 0,1,2 ... and calculate the deltas to do a quick fit.

But I thought of another scenario this morning where I think they come in particularly nicely and answer a long standing philosophical question of mine. There's a class of formulas that are usually proven inductively where one's often left asking: "How did someone find the original pattern to test?" As a student I would just play around, but now I see these more as curve fitting exercises.

A good example of this is the sum of squares \( \sum_{i=1}^{n}n^2   = \frac{n (n+1)(2n +1)}{6}\)

The inductive proof is not hard, and there are some beautiful visual versions (link to proof ) but it was always hard for me to think how this was actually discovered.   Enter the deltas ....

When looking for a formula we just need to generate enough values and see if the deltas resolve. If they do its a nth degree polynomial and we can work out the coefficients.

n   sum-of-squares  deltas

0    0
1    1            3
             4           2
2    5            5
             9           2
3   14           7
4   30

This shows its a 3rd degree polynomial of the form  \( Ax^3 + Bx^2 + Cx + D\)   

  • from f(0) = 0 we see D = 0 
  • from the deltas we see  \( A = \frac{2}{6!} = \frac{1}{3} \)  
  • We can then substitute in f(1) and f(2) to get a simple system \(B + C = \frac{2}{3} \) and \(4B + 2B = \frac{7}{3} \)
  • After solving we find: \( f(x) = \frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6} \)  which combines to exactly our original  \( \frac{n (n+1)(2n +1)}{6}\)

Note: you could also treat this like a linear system if you can tell what degree the function is likely to be but that's actually more work anyway in many cases.

No comments:

Post a Comment