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

1. Feb 15, 2015

### 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 ans, I want a function that satisfies f(n) ~ an as n -> infinity.

2. Feb 15, 2015

### Staff: Mentor

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

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

3. Feb 15, 2015

### japplepie

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

Last edited: Feb 15, 2015
4. Feb 15, 2015

### Staff: Mentor

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

5. Feb 15, 2015

### japplepie

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 = an+1-an
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

Last edited: Feb 15, 2015
6. Feb 15, 2015

### Staff: Mentor

Then 1010 and 1012 should be 110 and 112.
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.

7. Feb 15, 2015

### 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,...

Last edited: Feb 15, 2015
8. Feb 15, 2015

### Staff: Mentor

Still too many options for a general answer.

9. Feb 15, 2015

### japplepie

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 in to an algorithm that can search through all arithmetic rates of growths.
So, there's a chance that it's not impossible.

10. Feb 16, 2015

### Staff: Mentor

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.

11. Feb 16, 2015

### japplepie

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.

12. Feb 16, 2015

### Svein

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

13. Feb 16, 2015

### Staff: Mentor

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$.

14. Feb 17, 2015

### japplepie

$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

It works, but only for specific cases

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook