I was reading Stirling's approximation and got quite confused with the idea of asymptotic formula. So in Wikipedia it says that a function $F(n)$ of $n$ is asymptotic formula for $P(n)$ if $P(n)$ is asymptotically equivalent to $F(n)$ that is if $$\lim_{n\rightarrow\infty}\frac{P(n)}{F(n)}=1$$ my question is what is difference between this and $$F(n)\rightarrow P(n)$$
-
1$\begingroup$ Your functions will often go to $\infty$ as $n \to +\infty$ (especially using Stirling) which makes your second formulation much less appealing... (further the first formulation is more symmetric between $P(n)$ and $F(n)$). $\endgroup$– Raymond ManzoniCommented Dec 1, 2014 at 9:48
-
$\begingroup$ Short answer: the first is meaningful and the second isn't. "$F(n)\to P(n)$ as $n\to\infty$" is a misuse of limit notation. $\endgroup$– user147263Commented Dec 1, 2014 at 15:58
3 Answers
Consider $F(n) = n$ and $P(n) = n+\sqrt{n}$.
Note that $$\lim_{n \to \infty} (P(n)-F(n)) = +\infty \implies F(n) \not\to P(n)$$ whereas $$\lim_{n \to \infty} \dfrac{P(n)}{F(n)} = 1 \implies F(n) \sim P(n)$$
As $n \to \infty$, the statement that $F(n) \to P(n)$ is a more stronger statement than $\displaystyle\lim_{n \to \infty} \dfrac{P(n)}{F(n)} = 1$.
-
$\begingroup$ Since $n$ is changing, I am not sure $F(n) \to P(n)$ would be as meaningful or well-defined as $P(n)-F(n) \to 0$ $\endgroup$– HenryCommented Oct 21, 2023 at 5:17
The limit of a quotient of functions is the quotient of the limits (if the limits exist) so both way of writing would mean the same.
The problem of the second expression is that
$f(n) \rightarrow P(n)$ when $n \rightarrow \infty$ has no sense since the right part should be a number! (or you are speaking of convergence and f(n) is more a $f_n$. Then you have to take care of which convergence you want to deal with).
I hope i'm clear: don't use the latter ;)
Btw, @Raymond Manzoni 's answer is also a good one but i wanted to make clearer the non-sense of the latter expression
Note that we can reformulate $$\lim_{n\rightarrow \infty}\frac{P(n)}{F(n)}=1,$$ with a little bit of algebra as $$P(n)\underset{n\rightarrow\infty}{\sim} F(n)\Leftrightarrow \lim_{n\rightarrow \infty}\frac{P(n)-F(n)}{F(n)}=0.$$
That is the difference between the functions becomes negligible as $n\rightarrow\infty$.
For example consider $F(n)=10^n$ and $P(n)=10^n+1$. As $n$ gets big, the difference between them becomes negligible.
Similarly if you have €1,000.42 in your bank account you would just say you have €1,000 as the difference between them is relatively negligible.