0

Is this a valid proof?

Definition: $f\left(n\right)=\omega\left(g\left(n\right)\right)$ if $\underset{n\rightarrow\infty}{\lim}\frac{f\left(n\right)}{g\left(n\right)}=\infty$ for $f\left(n\right),g\left(n\right):\mathbb N\rightarrow\mathbb R^{+}$

Therefore: $\underset{n\rightarrow\infty}{\lim}\frac{2^{n}}{n}\stackrel{L'H\hat{o}pital}{=}\underset{n\rightarrow\infty}{\lim}\frac{2^{n}\ln\left(2\right)}{1}=\underset{n\rightarrow\infty}{\lim}2^{n}\ln\left(2\right)=\infty$

CStudent
  • 67
  • 1
    Yeah, that works, but L'Hopital is overkill. Just show $2^n\geq\frac{n(n-1)}2$ for all $n.$ You can prove that by induction, or combinatorially. If you want to use calculus, $$2^n=e^{n\log2}=\sum_{k=0}^\infty\frac{(n\ln 2 )^k}{k!}>\frac{\ln^22n^2}{2}.$$ – Thomas Andrews Mar 20 '23 at 20:08
  • 1
    Do this, for $k=1$. – Dietrich Burde Mar 20 '23 at 20:09
  • Your "therefore" comes out of the blue. It should occur later, in a complementary sentence: "Therefore, $2^n=\omega(n)$" – Anne Bauval Mar 20 '23 at 20:11
  • @ThomasAndrews Thanks! Yeah, I figured L'Hopital is overkill but it's the first thing that came in mind. – CStudent Mar 20 '23 at 20:12
  • 1
    $\frac{a_{n+1}}{a_n}=\dfrac{2n}{n+1}\to 2$ so for $n>n_0$ large enough $a_{n+1}>\frac 32 a_n$ and $a_n>(3/2)^{n-n_0}a_{n_0}\to\infty$ – zwim Mar 20 '23 at 20:14

0 Answers0