# Method of finite differences

This is a method for finding the nth term of a sequence. First make a table showing the differences, then the differences of the differences, etc, until you reach a row which is all zeros. (If you can't find a row which is all zeros, the method will not work.) For example:

 1 3 11 31 69 131 223 351 ...
 2 8 20 38 62 92 128 ...
 6 12 18 24 30 36 ...
 6 6 6 6 6 ...
 0 0 0 0 ...

Call the terms in the sequence a0, a1, a2 etc, the first differences b0, b1, b2 etc, the second differences c0, c1, c2 and so on:

 a0 a1 a2 a3 a4 a5 a6 a7 ...
 b0 b1 b2 b3 b4 b5 b6 ...
 c0 c1 c2 c3 c4 c5 ...
 d0 d1 d2 d3 d4 ...
 e0 e1 e2 e3 ...

The formula for the nth term of the sequence is: $${a}_{{n}}={a}_{{0}}+{b}_{{0}}{n}+{c}_{{0}}\frac{{{n}{\left({n}-{1}\right)}}}{{{2}!}}+{d}_{{0}}\frac{{{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}}}{{{3}!}}+{e}_{{0}}\frac{{{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}{\left({n}-{3}\right)}}}{{{4}!}}+\ldots$$

(Of course the formula stops when it gets to the row which is all zeros)

So applying this to the example above, we get: $${a}_{{n}}=1+2{n}+\frac{{6{n}{\left({n}-{1}\right)}}}{{{2}!}}+\frac{{6{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}}}{{{3}!}}$$

$${a}_{{n}}=1+2{n}+{3{n}{\left({n}-{1}\right)}}+{{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}}$$ $${a}_{{n}}={1}+{2}{n}+{3}{{n}}^{{2}}-{3}{n}+{n}{\left({{n}}^{{2}}-{3}{n}+{2}\right)}$$ $${a}_{{n}}={1}+{2}{n}+{3}{{n}}^{{2}}-{3}{n}+{{n}}^{{3}}-{3}{{n}}^{{2}}+{2}{n}$$ $${a}_{{n}}={1}+{n}+{{n}}^{{3}}$$ If you check this against sequences in the two boxes above, you will see that it works. However, it does rely on calling the term that starts the sequence the "zeroth term. If we need a formula in which the first term is a1, we just need to replace n by (n-1) everywhere it appears in the formula. So the nth term of the sequence above would be: $${a}_{{n}}={1}+{(n-1)}+{{(n-1)}}^{{3}}$$ $${a}_{{n}}={n}+{{(n-1)}}^{{3}}$$

[Of course we could go right back to the original formula and make this change, giving: $${a}_{{n}}={a}_{{1}}+{b}_{{1}}{(n-1)}+{c}_{{1}}\frac{{{(n-1)}{\left({n}-{2}\right)}}}{{{2}!}}+{d}_{{1}}\frac{{{(n-1)}{\left({n}-{2}\right)}{\left({n}-{3}\right)}}}{{{3}!}}+{e}_{{1}}\frac{{{(n-1)}{\left({n}-{2}\right)}{\left({n}-{3}\right)}{\left({n}-{4}\right)}}}{{{4}!}}+\ldots$$ But that tends to make the simplification harder.]

Here is an easier example, illustrating a different approach in which we extend the table backwards to create a "zeroth term.

 1st 2nd 3rd 4th 5th 6th ...
 2 5 10 17 26 37 ...
 3 5 7 9 11 ...
 2 2 2 2 ...
 0 0 0 ...

We extend this backwards, starting with the bottom row and working up:

 0th 1st 2nd 3rd 4th 5th 6th ...
 1 2 5 10 17 26 37 ...
 1 3 5 7 9 11 ...
 2 2 2 2 2 ...
 0 0 0 0 ...

Now the formula for the nth term is: $${a}_{{n}}=1+1{n}+\frac{{2{n}{\left({n}-{1}\right)}}}{{{2}!}}$$

$${a}_{{n}}=1+{n}+{{n}{\left({n}-{1}\right)}}$$ $${a}_{{n}}={1}+{n}+{{n}}^{{2}}-{n}$$ $${a}_{{n}}={1}+{{n}}^{{2}}$$