1

Suppose constant d>0. Prove d^n = O(n!) left to right prove only, is there any way to prove that other than using limit?

Lisa
  • 145

1 Answers1

1

Let $N\geq d$, $M=d^N/N!$. It follows that for $n>N$ $$ d^n=d^N d^{n-N}\leq d^N (N+1)\ldots (n-1)n=d^N\frac{n!}{N!}= M n! $$ since $d\leq (N+1)$, $d\leq (N+2)$, ..., $d\leq n$, and so $$ d^{n-N}=d\cdot d\cdot \cdots \cdot d\leq (N+1)(N+2)\ldots(n-1)\cdot n $$

Marcin Łoś
  • 2,613
  • I didn't understand the part after less than sign, can you clarify? – Lisa Feb 25 '14 at 21:15
  • 1
    Edited. Did it help? – Marcin Łoś Feb 25 '14 at 21:19
  • you assumed that d^n <= d^N*N, right? – Lisa Feb 25 '14 at 21:52
  • 1
    Hmm... I cannot see why would you say that. I assumed only $N\geq d$ and $n>$. The inequality between $d^{n-N}$ and this product comes from the fact, that $d^{n-N}$ has $n-N$ factors ($d$'s). First $d$ is less than $N+1$, second $d$ is less than $N+2$ etc, all the way to $n$. – Marcin Łoś Feb 25 '14 at 22:06