# How to use a difference table to find a formula for a given sequence?

Given a sequence, how do you get a "rule" from its difference table? For example;

1, 2, 3, 4, 5, 6
1, 1, 1, 1, 1

Or

1, 2, 7, 16, 29
1, 5, 9, 14
4, 4, 4

I haven't really explored this topic before, and cannot find much online (I think I'm bad at searching)

Also I need this for a Lua program on iPod, if it's worth mentioning

It’s really easy, if your sequence truly is given by a polynomial formula. First you have to know the Basic Functions $C_i$: \begin{align} C_0(n)&=1\quad\text{(constant)}\\ C_1(n)&=n\\ C_2(n)&=\frac{n(n-1)}2\\ C_3(n)&=\frac{n(n-1)(n-2)}{3!}\quad\text{etc.} \end{align}

You see that these functions take integer values for all integer values of $n$, even though their coefficients are not integral.

Now you write your sequence and the sequence of successive differences. Rather than explain in the abstract what you do, I’ll use the sequence of where $F(n)$ is the sum of the first $n$ squares (starting at zero). Our first sequence is $(0,1,5,14,30,\cdots)$, the sequence you’re interested in. The first differences are $(1,4,9,16,\cdots)$ (of course); the second differences are $(3,5,7,\cdots)$; and the third differences are constant $2$.

Now you look at the first entry in each list. These numbers are the coefficients of the functions $C_i$. In our example, these are $0$, $1$, $3$, and $2$. So your function is described as $C_1+3C_2+2C_3$. Expanding out you get $$F(n)=n + \frac{3n(n-1)}2+\frac{2n(n-1)(n-2)}6=\frac{2n^3+3n^2+n}6\,.$$ That’s the method. Now you go home and give your own proof that it works.

• What's 3! ${}{}{}$ Dec 28, 2014 at 14:31
• These are the factorials. So $n!$ is the product of the integers from $1$ through $n$ inclusive: $4!=1\cdot2\cdot3\cdot4=24$, etc. Dec 28, 2014 at 14:39
• Why are you using dots for multiplication and not $\times$ (or *) Dec 28, 2014 at 14:44
• Because that’s the mathematicians’ way. It’s just one of the many ways in which the notation of mathematics differs from the notation used by computer folks. Dec 28, 2014 at 14:52
• I've always know to use $\times$ on paper, and * on computer, what the heck is • Dec 28, 2014 at 14:56

By rule I think you meant the n$^{th}$ term of that sequence,

In any arithmetic sequence it is $\big(a+(n-1)d\big)$, where a is the first term and d is the common difference.

In your sequence it is, $\big(1+(n-1)1\big)=n$, that means that n$^{th}$ term of this sequence will be $n$.

In your second sequences the common difference between two consecutive term is in Arithmetic progression.

• I edited the question with a different table, if it makes this less valid. Dec 28, 2014 at 13:03
• I've answered the first part. Dec 28, 2014 at 13:09
• But how do I get the rule? Dec 28, 2014 at 13:14
• A rule is something that can be used to determine the nth term. Dec 28, 2014 at 13:18