Method

Unlike some of my more lengthy posts, this is just a brief post about a nifty trick on how to easily fit a polynomial to a set of $N$ values. 

I am hoping that the animated gif is fairly self-explanatory. However, here’s just a bit more detail.

Suppose you have are given the first few terms of a sequence;

$$ \{t_1, t_2,t_3,t_4,t_5,t_6,\ldots \} = {4,5,9,14,18,19,\ldots} $$

…And yes, I literally chosen random numbers for this example, so that you can see that even for seemingly horrendous sequences, we can derive the formula in an almost trivial way.

1. The first step is to take the successive differences of each term: $1,4,5,4,1,…$.
2. We then take the differences of these differences: $3,1,-1,-3,…$. Notice that we may get negative numbers. That is fine.
3. We then take the differences of these differences: $-2,-2,-2,…$.
4. And we keep doing this until the calculated differences are all zero, or until we get to the bottom of the pyramid.
5. We then identify the first term in each of these rows. These shall be our magical coefficients: $ 4,1,3,-2,0$.

$T_n$

Now the magical part begins.

To calculate the $n$-th term of the sequence, $T_n$, we simply combine these coefficients with successive binomial terms (ie successive terms in the $(n-1)$-th row of Pascal’s triangle.

We could leave it like this, because this is very elegant in itself. Or we can expand out the binomial terms and the simplify. Remember that 

$$\binom{n}{k} = \frac{n(n-1)…(n-k+1)}{k!} $$

The end result is that $T_n = (48-43n+21n^2-2n^3)/6$ 

You can check that substituting $n=1,2,3,4,5,6$ into this equation will produce $4,5,9,14,18,19$.

And we did this without breaking a sweat!

What this process does, is try to fit (interpolates) the data with polynomial of degree up to $n$. If the underlying data is represented by a polynomial of degree less than $n$, the pyramid will terminate at some stage with a row of zeroes. However, even if it doesn’t, this technique will fit a polynomial of precisely degree $n$ to these $n$ points. 

Some of you will notice that this is a cubic equation. So it is even more amazing that we derived a cubic equation without any difficult solving of variables, simultaneous equations, or any other difficult operation!

Here’s the same thing for a less obvious sequence. Notice in this case, it doesn’t terminate in a row of zeros. But that’s ok!

$S_n$

Some of you might have already seen this trick, but what is even less well known is that this technique can be trivially extended to calculate the sum of the first $n$ terms, $S_n$.

Instead of combining the derived coefficients $\{4,1,3,-2,…\}$ with the binomial coefficients $\binom{n-1}{0}, \binom{n-1}{1}, \binom{n-1}{2}, \binom{n-1}{3},…$, respectively we now need to combine them with the binomial coefficients$\binom{n}{1}, \binom{n}{2}, \binom{n}{3}, \binom{n}{4},…$

(The hint I give to readers as to why this works, is that it leverages the special property of Pascal’s triangle that is often affectionately called the “hockey stick”-formula, because the relevant entries in Pascal’s triangle carve out a shape that looks like a hockey stick.)

The end result is $S_n = {48-43n+21n^2-2n^3}/6$.

Again, you can plug $n=1,2,3,4,5..$ into this equation to obtain the cumulative sums of this series, $4,9,18,32,50,69,…$

I will leave it to the reader to prove why this method always work. However, if you get really stuck, try searching for the phrase “forward differences”, and/or ‘finite differences”

My name is Martin Roberts. I have a PhD  in theoretical physics. I love maths and computing. I’m open to new opportunities – consulting, contract or full-time – so let’s have a chat on how we can work together! Come follow me on Twitter: @Techsparx! My other contact details can be found here.

[mc4wp_form id=”1021″]

Other Posts you may like

• Trigonometry in Pictures
• Lissajous Curves
• Multiple Pendulums
• Theil-Sen and Siegel estimator for linear regression