How to solve for a function that is asymptotic to a sequence

[japplepie]

I have a sequence of natural numbers which is generated by a really complicated function.
This function only takes in natural numbers.

How do I solve for a function that is asymptotic to the sequence?
If I have a sequence of a_ns, I want a function that satisfies f(n) ~ a_n as n -> infinity.

 

[mfb]

That depends on the function. There is no general answer.

If a_n converges, then f(x)=a_[x] will work (using the floor function), but I guess that is cheating.

 

[japplepie]

That depends on the function. There is no general answer.

If a_n converges, then f(x)=a_[x] will work (using the floor function), but I guess that is cheating.

I'm trying to use this on things like these:

Input: 102, 104, 106, 108, 110, 112, ... ~ 2x
or
Input: 1, 30, 185, 886, 3855, 16064, ... ~ 4^x

 

[mfb]

Without more details, "finding some expression that looks correct" is the best approach.
The first one does not look like 2x.

 

[japplepie]

Without more details, "finding some expression that looks correct" is the best approach.
The first one does not look like 2x.

Actually the first one is 2x+100, which is asymptotic to 2x as x -> infinity
--------------------------------------------------------------
Isn't there any way of creating another series from the complicated one and doing "stuff" to it.

For instance, in my first example, I could do create another series bn = a_n+1-a_n
bn would be 2, 2, 2, 2, ...
The function that makes bn would be g(n)=2;

And I know that doing this subtraction thing is kind of taking the derivative from the ff:
f'(x) ~ f(x+1) - f(x) <- this is true for polynomial functions, idk about other kinds of functions though

and so, I could integrate (2 dx) which will give me 2x.

Basically, taking the "approximate derivative" to get a simpler sequence. Get the function for that sequence and do anti derivatives.

----------------------------------------------
This technique on another sequence:
1, 5, 11, 19, 29, 41, 55, 71, 89, 109, ...

(subtract)
4, 6, 8, 10, 12, 14, 16, 18, 20, ...
(subtract)
2, 2, 2, 2, 2, 2, 2, 2, ...
h(n) = 2
g(n) = 2x (anti derivative of h(n))
f(n) = x^2 (anti derivative of g(n))

and this method spits out x^2

 

[mfb]

Actually the first one is 2x+100, which is asymptotic to 2x as x -> infinity

Then 1010 and 1012 should be 110 and 112.

Isn't there any way of creating another series from the complicated one and doing "stuff" to it.

It can be possible to simplify your formula, but there is no magic trick that simplifies all formulas.
Taking the difference between two elements works well for linear series, doing that multiple times works for all polynomials, taking the ratio works well for exponential series, but there are so many series that are in none of those categories.

 

[japplepie]

My bad, sorry about the typo

I'm only limiting my series to series using arithmetic operations and their respective inverses

Series that are generated via addition, multiplication, exponentiation, ... subtraction, division, roots & logs,...

 

[mfb]

Still too many options for a general answer.

 

[japplepie]

Still too many options for a general answer.

By looking at the nth term of each iteration of doing the (subtraction or division or ...) process in the sequence, and put them in a sequence.

If this sequence doesn't converge to 0 (in case of linear) or 1 (for everything else), then it means that I'm going to need a higher inverse operation to capture the sequence.

For instance, if I do the subtraction process to a sequence generated from f(x)=2^x, sub(f(x)) -> 1, 2, 4, 8, 16, ... and sub(sub(f(x)) -> 1, 2, 4, 8, 16, ...

No matter how many times I iterate sub on this sequence, it never approaches 1.

Therefore, we need to check the next/higher inv. operation of sub which is div. ... If that doesn't work do the same thing using roots & logs

The process above can be formed into an algorithm that can search through all arithmetic rates of growths.
So, there's a chance that it's not impossible.

 

[mfb]

You still don't get all sequences with that approach (and having to guess what to do each step is not nice either). The worst case would be uncomputable functions but even floor(10*sin(x)) escapes all methods mentioned so far.

 

[japplepie]

You still don't get all sequences with that approach (and having to guess what to do each step is not nice either). The worst case would be uncomputable functions but even floor(10*sin(x)) escapes all methods mentioned so far.

There is a hierarchy of functions you could follow to be able to not guess the next step which goes like
iterated successor a.k.a Addition which has inverse sub
iterated addition a.k.a Multiplication which has inverse div
iterated multiplication a.k.a Exponentiation which has inverse log and root (there are two of them, since it isn't commutative)
iterated exponentiation a.k.a Tetration ...
...
...
...

And just go through straight down to get to the next step.

And also, I'm limiting to what I'm taking in as sequences which are generated by operations of these types; sequences derived from operations mentioned above.

Which means I'm not considering sines and cosines.

 

[Svein]

How do I solve for a function that is asymptotic to the sequence?
If I have a sequence of ans, I want a function that satisfies f(n) ~ an as n -> infinity.

Maybe difference equations can help. See for example http://en.wikipedia.org/wiki/Recurrence_relation .

 

[mfb]

There is a hierarchy of functions you could follow to be able to not guess the next step which goes like
iterated successor a.k.a Addition which has inverse sub
iterated addition a.k.a Multiplication which has inverse div
iterated multiplication a.k.a Exponentiation which has inverse log and root (there are two of them, since it isn't commutative)
iterated exponentiation a.k.a Tetration ...

Sometimes you'll need operations from different groups for the same sequence, applied in a specific order.

Sometimes your exact series is a sum of multiple components, so you never reach something "nice". And then you run into trouble:
$2^x+x^2$ - you can take the ratio, it will approach 2, but it will never be exactly 2.
$2^x floor(ln(x))$ - that will approach 2 as well in the ratio, but the function is certainly not $2^x$.

 

[japplepie]

Sometimes you'll need operations from different groups for the same sequence, applied in a specific order.

Sometimes your exact series is a sum of multiple components, so you never reach something "nice". And then you run into trouble:
$2^x+x^2$ - you can take the ratio, it will approach 2, but it will never be exactly 2.
$2^x floor(ln(x))$ - that will approach 2 as well in the ratio, but the function is certainly not $2^x$.

$2^x+x^2$ is asymptotic to $2^x$ so this is what I'm looking for; I'm not looking for the exact explicit answer, just an asymptotic function as x-> infinity

Maybe difference equations can help. See for example http://en.wikipedia.org/wiki/Recurrence_relation .

It works, but only for specific cases