3 ms·

Fun fact: Mathemetica has a method FindSequenceFunction which does exactly what you describe. In my experience, however, it generally requires at least 4 terms

Fun fact: Mathemetica has a method FindSequenceFunction which does exactly what you describe. In my experience, however, it generally requires at least 4 terms. 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} Which is the number of 0,1 sequences of length n that contain two adjacent 1s 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) Which, astonishingly, is correct for all the values I've tried. So apparently Mathematica understands more about this sequence than I do, and I know its definition. 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} Which is the integral x^n (1 - 2 x)^n for x from 0 to 1, for n = 0..<10. Here it seems 10 numbers are required. This yields the solution (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)!) Which as far as I can tell, is a closed-form solution (!) to the integral. A solution it worked out to an integral it has never seen, but only the first 10 elements in the sequence. So it's safe to say Mathematica knows a lot more about math than I do.

bovik 11y ago
For this purpose mathematicians use OEIS (oeis.org). Check it out.
thisrod 11y ago
Which is the number of 0,1 sequences of length n that contain two adjacent 1s 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.
- thisrod 11y ago
  OK, got it. 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.

bovik 11y ago

For this purpose mathematicians use OEIS (oeis.org). Check it out.

thisrod 11y ago

Which is the number of 0,1 sequences of length n that contain two adjacent 1s 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.

thisrod 11y ago
OK, got it. 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.