1. growth

1. Prove that $\log x$ grows more slowly than $x^c$ for any positive number $c$.

Proof. So for $x > (c+1)!$, we have $e^x > \frac{x^{c+1}}{(c+1)!} > x^c$. If we fix $c$ we could probably prove this by induction on $x$ (e.g. fix $c=1$). Now can we somehow "take inverses" to deduce that $\log x < x^c$ for any positive number $c$?

2. Prove that for any $c,d >1$, we have $c^x > x^d$ for all sufficiently large $x$.

Proof. Let $f(x) = c^x$ and $g(x) = x^d$. Since $f(x+1) = c^{x+1} = c^{x} \cdot c = cf(x)$, $f$ has exponential growth. And $g(x)$ has polynomial growth which is slower than exponential growth. Are these somewhat correct?

2. With the first one I would probably go with the limit route:

Take $\lim_{x \to +\infty} \frac{x^c}{ln(x)}$ , now, since both the numerator and denominator tend to infinity, we aply L'Hopital's rule and reach the equivalent $\lim_{x \to +\infty} {xx^{(c-1)}}$ which tends to infinity.

For the second one I don't see any problem with your argument if you already know (ie. have proven) that exponential growth is indeed faster than polynomial growth. At any rate the proof of that would be almost the same as the first one, only with $c^x$ instead of $ln(x)$ and the limit would then tend to zero (if you put the exponential in the denminator

3. Originally Posted by Jose27
With the first one I would probably go with the limit route:

Take $\lim_{x \to +\infty} \frac{x^c}{ln(x)}$ , now, since both the numerator and denominator tend to infinity, we aply L'Hopital's rule and reach the equivalent $\lim_{x \to +\infty} {xx^{(c-1)}}$ which tends to infinity.

For the second one I don't see any problem with your argument if you already know (ie. have proven) that exponential growth is indeed faster than polynomial growth. At any rate the proof of that would be almost the same as the first one, only with $c^x$ instead of $ln(x)$ and the limit would then tend to zero (if you put the exponential in the denminator
1. I don't think that's correct. First of all it's $\lim_{x \to \infty} cx^c = \infty$. But this says nothing about the inequality. I think the idea is to transform a given inequality we know to be true to the one that we want.

4. No, the correct one is the limit I wrote. What I'm trying to do is show that $x^c$ grows at a faster rate than $ln(x)$, which I did, because the limit is $\infty$. the limit you wrote indeed says nothing about what you're trying to do, but what you want is to compare $x^c$ and $ln(x)$.

Now if you want a proof based on the inequalities you gave, then, I'm not sure your inequalities are sharp enough, since the best you can get from them is $\frac{x}{c!} \leq ln(x)$

5. Originally Posted by Jose27
No, the correct one is the limit I wrote. What I'm trying to do is show that $x^c$ grows at a faster rate than $ln(x)$, which I did, because the limit is $\infty$. the limit you wrote indeed says nothing about what you're trying to do, but what you want is to compare $x^c$ and $ln(x)$.

Now if you want a proof based on the inequalities you gave, then, I'm not sure your inequalities are sharp enough, since the best you can get from them is $\frac{x}{c!} \leq ln(x)$
You're correct in showing the inequality. But the limit is wrong. $\lim_{x \to \infty} \frac{x^c}{\ln x} = \frac{\infty}{\infty}$. Now using L'hopitals rule, we get $\lim_{x \to \infty} \frac{cx^{c-1}}{1/x} = \lim_{x \to \infty} xcx^{c-1} = \lim_{x \to \infty} cx^{c} = \infty$.

6. Ah, you're right I forgot about the constant, but that doesn't matter, you're missing the interpretation of the limit. You have a quotient of two functions that tend to infinity as x increases, now if the limit of said quotient is infinity it means that the one in the numerator increased way more than the one in the denominator (if the limit was zero, then it would be the other way around). I guess it would be easier to understand if you wrote down what it means that said quotient limit goes to infinity (using epsilon-delta definition of limit).

$\forall R > 0 \exists r > 0$ such that if $x \geq r$ then $f(x) \geq R$.

Now $f(x)= \frac{x^c}{ln(x)}$ thus for $x \geq r$ we have $x^c \geq Rln(x)$. Since $R$ was arbitrary we can take $R \geq 1$ and thus the inequality you want is established.

7. Originally Posted by Jose27
Ah, you're right I forgot about the constant, but that doesn't matter, you're missing the interpretation of the limit. You have a quotient of two functions that tend to infinity as x increases, now if the limit of said quotient is infinity it means that the one in the numerator increased way more than the one in the denominator (if the limit was zero, then it would be the other way around). I guess it would be easier to understand if you wrote down what it means that said quotient limit goes to infinity (using epsilon-delta definition of limit).

$\forall R \geq 0 \exists r \geq 0$ such that if $x \geq r$ then $f(x) \geq R$.

Now $f(x)= \frac{x^c}{ln(x)}$ thus for $x \geq r$ we have $x^c \geq Rln(x)$. Since $R$ was arbitrary we can take $R \geq 1$ and thus the inequality you want is established.
yep and I noted that you showed that the inequality was correct.

8. Originally Posted by Sampras
yep and I noted that you showed that the inequality was correct.
What inequality?

9. Originally Posted by Jose27
What inequality?
Showing that since the limit is $\infty$, $\ln x < x^c$.

10. Oh yeah, I got confused for a moment.