Sequences and Series – Finding the nth Term Using Newton’s Little Formula

sequences-and-series

In a contest problem book, I found a reference to Newton's little formula that may be used to find the nth term of a numeric sequence. Specifically, it is a formula that is based on the differences between consecutive terms that is computed at each level until the differences match.

An example application of this formula for computing the nth term of the series (15, 55, 123, 225, 367, 555, 795, ….) involves computing the differences as shown below:

1) 1st Level difference is (40, 68, 102, 142, 188, 240)
2) 2nd Level difference is (28, 34, 40, 46, 52)
3) 3rd Level difference is (6, 6, 6, 6, 6) 

Now the nth term is $$15{n-1\choose 0} + 40{n-1\choose 1} + 28{n-1\choose 2} + 6{n-1\choose 3}$$ where the constant multipliers are the first term of the differences at each level in addition to the first term of the sequence itself.

I was not able to find any reference to this formula or a proof of it after searching on the web. Any explanation of this method is appreciated.

Best Answer

Suppose that we have a sequence:

$$a_0,a_1,...a_k$$

And we want to find the function of $n$ that defines $a_n$.

To do this we start by letting $a_{n+1}-a_n=\Delta a_n$ and we call this operation on $a_n$ the forward difference. Then given $\Delta a_n$ we can find $a_n$. Sum both sides of the equation from $n=0$ to $x-1$, and note that we have a telescoping series:

$$\sum_{n=0}^{x-1} \Delta a_n=\sum_{n=0}^{x-1} (a_{n+1}-a_n)=a_{x}-a_{0}$$

Hence $a_n=a_0+\sum_{i=0}^{n-1} \Delta a_i$. Also $\Delta a_n=\Delta (0)+\sum_{i=0}^{n-1} \Delta^2 a_n$...and so forth. Using this we must have if the series converges:

$$a_n=a_0+\Delta (0) \sum_{x_0=0}^{n-1} 1+\Delta \Delta (0) \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1+\Delta \Delta \Delta (0) \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1} 1+\cdots$$

Where $\Delta^i (0)$ denotes the first term ($n=0$) of the $i$ th difference sequence of $a_n$.

Through a combinational argument, If we take $\Delta^0 (0)=a_0$ and ${n \choose 0}=1$ we may get:

$$a_n=\sum_{i=0}^{\infty} \Delta^i(0) {n \choose i}$$

If it is the case you want the sequence to start with $a_1$ we need to shift this result to the right one:

$$a_n=\sum_{i=0}^{\infty} \Delta^i(1) {n-1 \choose i}$$

Note when you re-define $a_0$ to be $a_1$ by shifting it's index to the right one, you're re-defining $a_1-a_0=\Delta^1(0)$ to be $a_2-a_1=a_{1+1}-a_{1}=\Delta^1(1)$.