# Given a set, what process is there to trace back to the equation that generates it?

I was recently working on a piece of software and needed to know the number of different ways that a particular word could be represented in mixed upper-and-lowercase letters. For example, the word "bar" could be represented as:

{bar, Bar, bAr, baR, BAr, bAR, BaR, BAR}.

Or, more generally, let 0 = lowercase and 1 = uppercase:
{000, 100, 010, 001, 110, 011, 101, 111}

I did a few of these and figured out that:
f(1) = 2
f(2) = 4
f(3) = 8
f(4) = 16

Which any computer programmer instantly recognizes as f(n) = 2^n

But what if I hadn't been that lucky and my data had resulted in something like:

f(1) = 2
f(2) = 7
f(3) = 24
f(4) = 77

Is there some sort of process that I could use to discover the function?
( Which, in this example, is f(n) = (3^n) - n)

-
This is my first question on math.SE. Mods, please feel free to edit my question mercilessly if I've made mistakes. – Steve V. Jan 10 '11 at 5:39

No, there is no process.

The reason is simple: given any $k$ numbers $a_1,\ldots,a_k$, I can come up with a formula $f$ with $f(1)=a_1$, $f(2)=a_2,\ldots,f(k)=a_k$; for example, Lagrange Interpolation will produce a polynomial of degree $k-1$ that evaluates to these values; so you can take any other number $a_{k+1}$, and come up with a polynomial of degree $k$ that produces the same first $k$ values, and with $f(k+1)=a_{k+1}$. So you have at least as many polynomials of degree at most $k$ that generate the list you started with as there are real numbers, all of them distinct.

In fact, I could say that you "recognized" your first $f$ "incorrectly", since it is well known that the next term in the sequence is $31$, not $32$ (there are two ways to obtain $31$: one by using the Lagrange Interpolation Formula; the other is to consider what happens if you place $n+2$ points on a circle and join them all with lines; $f(n)$ is the number of regions into which the circle is divided. See Sequence A000127 in the On-Line Encyclopedia of Integer Sequences. See Carl Linderholm's Mathematics Made Difficult).

-
@Steve: now that you know this, you might be tempted to say "well, is there a way to find the 'simplest' process that generates a sequence," and the answer is still no even for a completely rigorous definition of 'simplest': this is a form of the non-computability of Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). – Qiaochu Yuan Jan 10 '11 at 15:03
It took me a bit of thinking, but I'm pretty sure I'm picking up what you're putting down. Thank you for the help! – Steve V. Jan 11 '11 at 3:38
@Steve V.: Glad I could help. – Arturo Magidin Jan 11 '11 at 3:42

In general there isn't one method for matching an equation to a set of numbers and furthermore for any finite sequence there are infinitely many equations that describe the sequence. There are a lot of tools and different ways of looking and sequences to find equations that seem like a "good fit". I would guess though that you would be best served by searching the encyclopedia of sequences or just typing your sequence into wolfram alpha.

-
I wish I could pick two answers as accepted - your answer was a little less detailed, but much easier to understand. (I honestly flipped a coin to decide between the two of them.) Thanks very much! – Steve V. Jan 11 '11 at 3:30

In general, you can have any number of functions satisfy a given pattern; if you don't know anything about the function, you won't be able to solve for it.

If you do know something about the function - for example, that it's an $n$-th degree polynomial - you would be able to solve for it (in this case if you have $n$ distinct values). But, what you know has to be pretty specific - for example, if you have $n$ points and you know you're looking for a polynomial function, but you don't know its degree, you'll have infinitely many functions to choose from that fit those points. (Furthermore, even if you do know its degree, but you have fewer points than the degree of the polynomial, you'll still wind up with infinitely many functions; and of course not everything is a polynomial).

-

Look it up at the OEIS. If nothing else, you'll gain a new appreciation for how many terms you need to make a sequence unique (as far as the OEIS is concerned).

By the way, many sequences that count lengths of words that you'll run into as a computer programmer are going to be regular languages, that is, they are described by a regular expression (equivalently, recognized by a finite state machine). There is a very well-understood theory of how to count these lengths; I don't think it is covered in computer science textbooks (for example it's not covered in Sipser), but there is some information in the relevant section of Stanley's Enumerative Combinatorics (rational generating functions), as well as Flajolet and Sedgewick's Analytic Combinatorics. I also briefly describe how this works in a few special cases in my notes on generating functions.

In other words, the approach I'm advocating is to figure out what the sequence is instead of trying to guess it. In your example, can you prove that $f(n) = 2^n$?

-
I think I could prove it, but the margin of this page is much too small... (: Thanks for the help! – Steve V. Jan 11 '11 at 3:51

As others have said, there can be many different formulas that will generate the terms of the sequence that you already know but give different results for other terms, and the OEIS is a good resource for looking up sequences.

Another technique that can be of use is the method of finite differences, briefly described in my answer here. In particular, if you have reason to believe that the sequence has a polynomial or exponential formula, finite differences can help determine the specific formula.

-