# Asymptotic Rate of Growth

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.

Edit

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

-
Isn't it O(x^3)? – Dr. belisarius Oct 8 '12 at 1:06
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? – Eric Brown Oct 8 '12 at 1:14
For polynomials, this answer or this answer might be what you're looking for. Possible duplicate – R. M. Oct 8 '12 at 1:17
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}] – R. M. Oct 8 '12 at 1:48
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]]. – J. M. Oct 8 '12 at 3:23

## 1 Answer

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}]
]


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]]


-
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]] – Daniel Lichtblau Jan 9 '14 at 23:40
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.) – Daniel Lichtblau Jan 9 '14 at 23:42
@DanielLichtblau Thanks! I had some spare time which coincided nicely with rm-rf's clean-up call. – Sjoerd C. de Vries Jan 10 '14 at 22:05