2
$\begingroup$

I am interested in proving or finding a counter example for the following statement

$$ \lim_{n \to \infty}{\frac{\ln{f(n)}}{\ln{g(n)}}} = \infty \implies \lim_{n \to \infty}{\frac{f(n)}{g(n)}} = \infty $$

It seems to make a lot of sense, but it isn't very clear how to prove this statement.

If it isn't true, what if both $f(n)$ and $g(n)$ are monotonically increasing?

I've tried looking at the contrapositive, as well as Taylor series expansions, but I'm not able to come to a complete conclusion.

I would also imagine that this holds for any monotonic function, not just the logarithm (if it holds at all).

$\endgroup$
  • $\begingroup$ If $f(n)=2$ and $g(n)=1+\frac{1}{n}$, you have a counter example. $\endgroup$ – Pierre Alvarez Sep 12 '14 at 18:22
1
$\begingroup$

I already gave a counter example in the comments for the general case.

let's suppose that f and g are monotonically increasing and >1. Then their limits is $+\infty$.(otherwise, the limit of $\frac{ln(f(n))}{ln(g(n))}$ would not be $+\infty$)

Let's define h such as : $f(n)=h(n)g(n)$

Then : $\frac{ln(f(n))}{ln(g(n))}=\frac{ln(h(n)g(n))}{ln(g(n))}=1+\frac{ln(h(n)}{ln(g(n))}$. So you know that the limit of $\frac{ln(h(n)}{ln(g(n))}$ is $+\infty$.

Since the limit of $ln(g(n))$ is $+\infty$, the limit of $ln(h(n))$ is also $+\infty$.

Hence, by definition of $h$, the limit of $\frac{f(n)}{g(n)}$ is also $+\infty$.

Is it ok for you?

$\endgroup$
  • $\begingroup$ Very simple and beautiful answer. +1 $\endgroup$ – Paramanand Singh Sep 13 '14 at 4:52
  • $\begingroup$ I think it is not necessary that $\log(g(n))$ also tends to $\infty$. It may tend to a finite limit. But your conclusion and proof holds in exactly the same manner. $\endgroup$ – Paramanand Singh Sep 13 '14 at 4:56
  • $\begingroup$ Very good, thank you. $\endgroup$ – RJTK Sep 13 '14 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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