2
$\begingroup$

How can I calculate the Asymptotic Rate of growth of a function, for instance like:

$X^3 - X^2 - X -1$

EDIT:

For instance, as you can see in this graph, after the 1200 the function approximates to the limit. I want to if there is a easy way to calculate the rate of grow, after 1200 for instance.

enter image description here

Edit

I'm trying to find a generalized way in order to graphically find it for Fibonacci, Tribonacci, Tetranacci sequences

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Isn't it O(x^3)? $\endgroup$
    – Dr. belisarius
    Oct 8, 2012 at 1:06
  • $\begingroup$ Are you asking for a generalized way of determining which term, e.g. x^3, x^2, x, or 1 grows fastest as x increases? $\endgroup$
    – Eric Brown
    Oct 8, 2012 at 1:14
  • $\begingroup$ For polynomials, this answer or this answer might be what you're looking for. Possible duplicate $\endgroup$
    – rm -rf ♦
    Oct 8, 2012 at 1:17
  • 5
    $\begingroup$ It doesn't happen all of a sudden at 1200... it's just that the plot range is such that it seems it is that way. As a hint, look at LogPlot[Fibonacci[n], {n, 0, 1500}] $\endgroup$
    – rm -rf ♦
    Oct 8, 2012 at 1:48
  • 2
    $\begingroup$ All the $n$-nacci sequences have exponential behavior; the base of their dominant exponential term is (expressed in Mathematica notation) Root[x^n - Sum[x^k, {k, 0, n - 1}], Mod[n, 2, 1]]. $\endgroup$
    – J. M.'s eventual burnout ♦
    Oct 8, 2012 at 3:23

1 Answer 1

Reset to default
3
$\begingroup$

As J.M. mentioned in the comments:

All the n-nacci sequences have exponential behavior; the base of their dominant exponential term is (expressed in Mathematica notation) 

Root[x^n - Sum[x^k, {k, 0, n - 1}], Mod[n, 2, 1]]

Demonstration:

With[{n = 2},
 base = Root[x^n - Sum[x^k, {k, 0, n - 1}], Mod[n, 2, 1]] // N;
 DiscretePlot[Fibonacci[x]/base^x, {x, 1, 40}, PlotRange -> {0, 0.7}]
 ]

Mathematica graphics

Daniel Lichtblau adds that Mathematica is able to calculate the Fibonacci series development at infinity:

Simplify[Normal[Series[FunctionExpand[Fibonacci[x]], {x,Infinity,2}]], 
         Assumptions->Element[x,Integers]]

Mathematica graphics

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Could take the series at infinity for cases like Fibonacci, where we have a closed form. This gives some exponential stuff: Simplify[Normal[Series[FunctionExpand[Fibonacci[x]], {x,Infinity,2}]], Assumptions->Element[x,Integers]] $\endgroup$
    – Daniel Lichtblau
    Jan 9, 2014 at 23:40
  • $\begingroup$ PS Thanks for taking so much time to respond to several unanswered posts. I noticed you've handled quite a few in the past day or two. (Maybe others before that, but I wasn't noticing then.) $\endgroup$
    – Daniel Lichtblau
    Jan 9, 2014 at 23:42
  • $\begingroup$ @DanielLichtblau Thanks! I had some spare time which coincided nicely with rm-rf's clean-up call. $\endgroup$
    – Sjoerd C. de Vries
    Jan 10, 2014 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.