¿Cómo puedo probar que $2^n=O(n!)$?
Es este un argumento válido?
2<=2,
2<3,
2<4,....
2<n if n>2
therefore 2.2.2....n times < 1.2. ... n
so,2^n <n!
Gracias de antemano.
¿Cómo puedo probar que $2^n=O(n!)$?
Es este un argumento válido?
2<=2,
2<3,
2<4,....
2<n if n>2
therefore 2.2.2....n times < 1.2. ... n
so,2^n <n!
Gracias de antemano.
El argumento es muy informal y tiene un pequeño agujero en él, pero la idea básica es correcta. El agujero se encuentra en el hecho de que $2^n$ es en realidad más grande que $n!$ para $n=1,2,3$. Correctamente usted debe demostrar por inducción sobre $n$ que $2^n\le n!$ para $n\ge 4$ y concluir de inmediato que $2^n$ es $O(n!)$.
$$(1)\;\;\text{Look at the positive series}\;\sum_{n=1}^\infty\frac{2^n}{n!}$$
$$(2)\;\;\frac{a_{n+1}}{a_n}=\frac{2^{n+1}}{(n+1)!}\cdot\frac{n!}{2^n}=\frac2{n+1}\xrightarrow[n\to\infty]{}0 \;,\;\text{thus} $$
$$(3)\;\;\text{The series in (1) converges}$$
$$(4)\;\;a_n=\frac{2^n}{n!}\xrightarrow[n\to\infty]{}0$$
Por tanto, para algunos
$$N\in\Bbb N\;\;\text{and}\;\;\forall n>N\;,\;\;\frac{2^n}{n!}<1\implies 2^n=\mathcal O(n!)$$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.