Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 15, 2015 #1
    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. jcsd
  3. Feb 15, 2015 #2

    mfb

    User Avatar
    2016 Award

    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.
     
  4. Feb 15, 2015 #3
    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
  5. Feb 15, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Without more details, "finding some expression that looks correct" is the best approach.
    The first one does not look like 2x.
     
  6. Feb 15, 2015 #5
    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
  7. Feb 15, 2015 #6

    mfb

    User Avatar
    2016 Award

    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.
     
  8. Feb 15, 2015 #7
    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
  9. Feb 15, 2015 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Still too many options for a general answer.
     
  10. Feb 15, 2015 #9
    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.
     
  11. Feb 16, 2015 #10

    mfb

    User Avatar
    2016 Award

    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.
     
  12. Feb 16, 2015 #11
    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.
     
  13. Feb 16, 2015 #12

    Svein

    User Avatar
    Science Advisor

    Maybe difference equations can help. See for example http://en.wikipedia.org/wiki/Recurrence_relation .
     
  14. Feb 16, 2015 #13

    mfb

    User Avatar
    2016 Award

    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##.
     
  15. Feb 17, 2015 #14
    ##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




Similar Discussions: How to solve for a function that is asymptotic to a sequence
Loading...