I'm not totally sure how the math behind it works (maybe it's similar to Eureqa?) but the results speak for themselves and are rather incredible.

For example, if I run FindSequenceFunction on this input:

    {0, 1, 3, 8, 19, 43, 94, 201, 423, 880}

Mathematica produces the result:

    1/10 (5 2^(1 + x) - 5 (1/2 - Sqrt[5]/2)^x + 
    3 Sqrt[5] (1/2 - Sqrt[5]/2)^x - 5 (1/2 + Sqrt[5]/2)^x - 
    3 Sqrt[5] (1/2 + Sqrt[5]/2)^x)

Another party trick is to use the input

    {-(1/6), 2/15, -(13/140), 23/315, -(83/1386), 305/6006, -(2269/
     51480), 4259/109395, -(16103/461890), 30616/969969}

    (2^(-2 - 3 x)
    x! (Sqrt[\[Pi]] (1 + x)! + 
    3 (-1)^x 2^(
    2 + 3 x) (1/2 (1 + 2 x))! Hypergeometric2F1[1, 3/2 + x, 
    2 + x, -8]))/((1/2 + x)! (1 + x)!)

So it's safe to say Mathematica knows a lot more about math than I do.

It sounds a lot simpler than that. There are n-1 places to put the adjacent 1s. For each of those, there are 2^(n-2) ways to complete the sequence with 0s and 1s. So the answer should be (n-1)*2^(n-2).

Edit: it isn't quite that simple, I'm counting sequences with multiple pairs of 1s multiple times.

By the way, Mathematica's formula looks a lot like the closed form for the Fibonacci sequence.

Let a_n be the number of sequences of 0s and 1s of length n, that do not contain a pair of 1s, and end in 0. Let b_n be similar, except that the sequences end in 1. These satisfy the recurrences a_{n+1} = a_n + b_n, and b_{n+1} = a_n. It follows that a_n satisfies the Fibonacci recurrence a_{n+1} = a_n + a_{n-1}. Starting from a_1 = 1, and a_2 = 2, we have a_n = F_{n+1}.

The total number of sequences of length n is 2^n, so the number we want is 2^n - a_n - b_n = 2^n - F_{n+1} - F_n = 2^n - F_{n+2}.

And this time it works :-). There might be a point about confirmation bias here, in that the trick is to count sequences that _don't_ contain a pair of 1s.

One drawback of Mathematica is that it has a very poor idea of the formulae that human readers will regard as simple.

Choose a programming language. Choose a sequence prefix (in your example: 2, 3). Then consider all the programs that accept n as input and output a sequence of n numbers, such that the first numbers are always 2, 3. Now take the shortest of those programs. The sequence it produces is the "simplest".

If this sounds tedious to code, you could easily outsource via Odesk or something.

It's uncomputable in general.

[1] http://www.amazon.com/Fluid-Concepts-And-Creative-Analogies/...

Generating functions provide a general framework for describing sequences, solving recurrence relations, etc.