# How can I write an equation that matches any sequence?

One thing I have been wondering about lately is how to write an equation that describes a pattern of numbers. What I mean is:

x   0    1    2
y   1    5    9


If I have this, I can tell that an equation that describes this would be y=4x+1. In fact, I don't even need the 3rd pair of numbers. It's very easy when the equation is a straight line. But when the equation is a parabola, its not always that easy. For example:

x   0    1    2
y   1    2    5


I can tell this is y=x2+1, because I recognize the pattern. But I can't always tell just by looking at the numbers what the right equation should be. Is there some way to always know the right equation? I know that if you get the x=0 term you can get the c in y=ax2+bx+c, but that's not enough to let me solve it like I can when the equation is just a line.

For example, can someone show me how you would do it for

x    0     1     2
y    5     4     7


It's not a homework question, I promise!

-
Are you interested in interpolation techniques such as the DFT? I am not prepared to write anything worthwhile about this, and there are many more interpolation techniques (some of which have already been discussed below). But interpolation is a topic we should have a canonical set of responses for (i.e. seeded and then answered in community wiki...) –  Tom Stephens Jul 25 '10 at 21:51
@Tom: I don't know how appropriate that would be for a question tagged middle-school... –  Larry Wang Jul 26 '10 at 8:21
Indeed. –  Tom Stephens Jul 26 '10 at 13:16

If you know your relationship is going to be a polynomial, then there are some pretty (conceptually) simple ways you can do this.

If you know what degree your polynomial is (line, parabola, cubic, etc.) then your job will be much easier. But if not, then you simply need to look at the number of points you have.

• If you are given one point, the best you can do is of degree 0 ( y = k )
• If you are given two points, the best you can do is of degree 1 ( y = A x + B )
• If you are given three points, the best you can do is of degree 2 ( y = A x2 + B x + C )
• If you are given four points, the best you can do is of degree 3 ( y = A x3 + B x2 + C x + D )
• etc.

When I say "the best you can do", what I mean is -- if you have a parabola, but are only given two points, then you really can't identify the parabola. But you can say that it's a simple line.

Let's assume you have three points. The "best you can do" is assume that it is degree 2. If it is actually of degree one, your answer will magically turn into a line ( your x^2 coefficient will be 0 )

The basic idea of solving relationships/equations is:

If you have n unknowns, you need n equations/points.

Notice how, in the form of the Parabola ( y = A x2 + B x + C ), you have three unknowns? And also three equations! (points)

Let's pick three arbitrary points

x   1    2    4
y   6    7    3


You would set up three equations:

6 = 12 * A + 1 * B + C

7 = 22 * A + 2 * B + C

3 = 42 * A + 4 * B + C

Three equations, three unknowns. You should be able to solve this with a combination of most system-of-equation-solving rules.

In our case, we find:

A = -1
B = 4
C = 3


So our equation is y = -x2 + 4 x + 3

Note that, if your original three points formed a line, your $A$ would $= 0$

However, if your equation is NOT a polynomial, then you are left with little more than guess and check, plugging in various coefficients and trials (exponential? trigonometric?)

The beauty of the polynomial approach is that a polynomial of high enough degree will always fit any list of points. (provided that the points form a function)

-
Thanks for the answer! I don't think anything you wrote is complicated enough to require special math formatting. Superscripts can be written in markdown by using <sup></sup> tags. This will probably improve readability for the average viewer because some people will not have the custom script installed. –  Larry Wang Jul 24 '10 at 21:54
Solving a system of linear equations isn't actually required here (although it certainly works). You can actually just write down the answer. See en.wikipedia.org/wiki/Lagrange_polynomial for details. Note that the answer you get by this method will always match the result you get from solving the system of equations. –  Simon Nickerson Jul 27 '10 at 5:23
Actually, the process of constructing the interpolating polynomial (whatever the format) is the implicit solution of a (dual) Vandermonde linear system; it's just that the special structure of the problem allows us to do better than the effort needed for Gaussian elimination. –  Ｊ. Ｍ. Jul 14 '11 at 11:24

Given a list of terms of a sequence as you describe, one technique that may be of use (supplementary to Justin's answer) is finite differences. Calculate the differences between successive terms. If these first differences are constant, then a linear equation fits the terms you have. If not, compute the differences of the differences. If these second differences are constant, then a quadratic equation fits the terms you have. If not, you can continue to compute differences until you reach a constant difference (in the nth differences means an nth degree polynomial), differences that are a constant multiple of the previous differences (exponential of some sort), or you run out of terms. In any case, what you find is limited to matching the terms you know, as without some kind of general rule for the sequence, the first unknown term could be anything and completely alter the pattern (and with n known terms, a polynomial of degree n-1 will always perfectly fit).

-
That's a good tip. Do you have a link to a demonstration, or could you post a simple one yourself? –  Larry Wang Jul 24 '10 at 23:24
The wikipedia page (en.wikipedia.org/wiki/Finite_differences) goes into a bit more depth (and there is more depth to go into--I just skimmed the surface of what can be a discrete differential calculus); the MathWorld page (mathworld.wolfram.com/FiniteDifference.html) may be a bit more useful (the thing labeled (7) is more or less what I do when I apply finite differences). –  Isaac Jul 25 '10 at 4:54
of course this works only if you (like it was asked in the question) have samples of the functions at 0,1,2,... or at least successive values of x (or values whose difference is constant - in both cases a simple change of variables does the trick). While finite differences is a powerful technique, you cannot use them directly if you are given the values of the function at x=0,1,4,9,15 :-) –  mau Jul 25 '10 at 20:44
@mau: I omitted that part as the original question asked about sequences, but you are correct that you need equally-spaced inputs for it to work as I've described and would have to do more work if the inputs were not equally-spaced. –  Isaac Jul 25 '10 at 22:19

In the general case of trying to predict some infinite sequence of integers, there is no formula. This is because there is no reason to expect a pattern to continue, since all sequences are possible.

However, you can say a certain number is more likely given a set of functions. For instance if you considered all Turing machines, you could say that given n elements of a sequence look at all the Turing machines that predict the current sequence, and then find the most predicted next number. There still isn't a efficient way to compute what the most likely next number is.

Ray Solomonoff called this "Universal Probabilistic Induction"

This is explained in more depth here: http://en.wikipedia.org/wiki/Inductive_inference

-

Of course there are infinite equation (even if you require them to be infinitely differentiable...) that satisfy the given constraints. As Isaac and Justin already wrote, you may always find a polynomial of degree at most n-1 (where n is the number of points given) which satisfies the given data; but you cannot be sure that this is the right answer. Moreover, if data is not exact but approximate the resulting polynomial may be quite different from the correct function, since it would likely hade huge peaks and falls. In such cases, an approximate method like least squares could be more useful.

-
+1 for mentioning overfitting (even if you didn't say the word) –  Larry Wang Jul 25 '10 at 21:21