# Patterns in Sequences

I've heard in a movie that for any sequence of numbers, there is a nice formula for generating that sequence. So, for example if I write:

1,2,1,2,3,3,1,2,3,1,2,4,...

There is a formula for generating it, though it is not an obvious one (to me). Where as

1,1,2,3,5,8, ...

is simply the fibonacci sequence with a(n) = a(n-1) + a(n-2). If the above is true, could you point me to some papers about it? I understand elementary number theory and some abstract algebra.

Thanks. I want to apply this to patterns in music.

EDIT: (How are you supposed to reply?)

Yes, finite sequences. What I mean is for any sequence that can be given, that asks for a formula, it's usually given in finite form, with ellipses indicating that it can be continued or that there is a pattern. And in music, you're usually dealing with finite songs. So yes, finite. Sorry for my lack of mathematical rigor, I've been out of the math mode for a few months. I'll pick up the ball soon enough! :D

So, again, a formula that accounts for the finite sequence given (at least), or one that could also give the rest of the sequence (which could be anything really) - it really doesn't matter for my uses.

Thanks for the quick responses. These stack exchanges are truly the best resources for info exchange, help, and community.

-
"Any" is quite the stretch... –  Guess who it is. Sep 23 '11 at 5:09
I've edited the OP. –  Dan Donnelly Sep 23 '11 at 5:26
Very relevant: math.stackexchange.com/questions/656/… –  anon Sep 23 '11 at 5:33
Thanks, anon. That's a refresher. I already knew about polynomial interpolation. I have to rethink what I'm actually looking for. –  Dan Donnelly Sep 23 '11 at 5:46
Dan, if you have a finite sequence, then you can just re-interpret it as a function with known values at inputs $k=1,2,3,\dots,n$. Does that work for you? –  anon Sep 23 '11 at 5:54

The statement that any sequence of numbers has a formula is not a precise statement, but any precise version I can think of for it is false.

For instance, here's one problem. This will only make sense if you understand different orders of infinity. There are only countably many possible formulas (for any meaning of the word formulas). However, there are uncountably many difference sequences of numbers. Thus there have to be sequences of numbers that cannot be expressed by a formula. In fact, "most" sequences of numbers cannot be expressed via a formula.

EDIT : OK, the OP wants a formula for finite sequences. Here's one way to do it which yields a polynomial function. Assume that the sequence is $a_1,\ldots,a_n$. For $1 \leq i \leq n$, define a polynomial $$f_i(x) = \frac{\prod_{j=1}^n (x-j)}{x-i}.$$ This is a polynomial -- the effect of the denominator is to cancel out the $x-i$ factor from the numerator. The polynomial $f_i(x)$ has the property that $f_i(j) = 0$ for $j \neq i$ and $f_i(i) \neq 0$. Now define $$g_i(x) = \frac{1}{f_i(i)} f_i(x).$$ We thus have $g_i(j) = 0$ for $j \neq i$ and $g_i(i)=1$. The desired function is then $$H(x) = \sum_{i=1}^n a_i g_i(x).$$

-
Well, there is one version of the statement I can think of that is true: finite sequences. (And I think this is likely the idea behind whatever movie character's statement is being alluded to.) –  anon Sep 23 '11 at 5:08
@anon: "movie character"? –  The Chaz 2.0 Sep 23 '11 at 5:11
@The Chaz: The OP said he heard this statement in a movie, which presumably means it was uttered by one of the movie's characters... –  anon Sep 23 '11 at 5:12
OK, it is true for finite sequences. But neither of the examples to OP gave were finite sequences, so I assumed that his definition of sequences included infinite sequences. –  Adam Smith Sep 23 '11 at 5:17
Yeah, finite sequences will do. –  Dan Donnelly Sep 23 '11 at 5:27

In practice, one thing you can try is to look up the sequence in the OEIS. Another possibility is to use Maple's gfun package. Neither of those work for your example 1,2,1,2,3,3,1,2,3,1,2,4, I suspect because that's just a made-up sequence that doesn't have any particular pattern behind it. On the other hand, perhaps these first 12 numbers just repeat, in which case there is a "simple" formula of the form $a_n = \sum_{j=0}^{11} c_j \exp( j n \pi i/6)$ for some constants $c_0, \ldots, c_{11}$.

-

Unfortunately I don't know the pattern of the sequence from movie

In general, if you interested in Pattern for Sequences you can start from here

http://en.wikipedia.org/wiki/Recurrence_relation

-