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.