Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By Archie

Thread: Proof that A^n < N!

  1. #1
    Newbie
    Joined
    Mar 2017
    From
    USA
    Posts
    3

    Question Proof that A^n < N!

    For any positive integer A, there is an integer N, which of course can vary depending on A, so that for all n >= N, A^n < n!.
    How am I supposed to show this? Do I need to show A^n = Big-O of n! or use induction? I tried both and I can't seem to figure it out.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,900
    Thanks
    636

    Re: Proof that A^n < N!

    For $\displaystyle k > A^2$ what happens to $\displaystyle \frac{k!}{A^k}$ as $\displaystyle k$ increases?
    Last edited by Archie; Mar 8th 2017 at 01:56 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2017
    From
    USA
    Posts
    3

    Re: Proof that A^n < N!

    I understand that n! increases at a faster rate than A^n, but how do I write that as a formal proof if I have to prove that n! increases at a faster rate? I tried doing a limit, but I can't use L'hopitals rule on the factorial because I can't use derivate (other than for log() and polynomials).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,900
    Thanks
    636

    Re: Proof that A^n < N!

    Ok. Suppose that $\displaystyle N > A^2$ and $\displaystyle \frac{N!}{A^N} = c$. Then for $\displaystyle n=N+k$

    $\displaystyle \frac{n!}{A^n} = \frac{(N+k)!}{A^{N+k}} > \frac{N!A^{2k}}{A^N A^k} = \frac{N!}{A^N}A^k = cA^k$

    For $\displaystyle A > 1$, the final expression above is clearly increasing without bound and so for all sufficiently large $\displaystyle k$ it is greater than 1.

    You can do $\displaystyle A=1$ separately.
    Last edited by Archie; Mar 8th 2017 at 04:42 PM.
    Thanks from sm99
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2017
    From
    USA
    Posts
    3

    Re: Proof that A^n < N!

    Thank you! This makes a lot of sense!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,141
    Thanks
    475

    Re: Proof that A^n < N!

    Presumably you know calculus and the fact that for any A
    $$e^A=\sum_{n=0}^{\infty}{A^n\over n!}$$
    In particular,
    $$\lim_{n\to\infty}{A^n\over n!}=0$$
    So let $\epsilon=1$ in the definition of limit and you get that there exist $N$ such that for all $n\geq N$,
    $${A^n\over n!}<1$$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: Feb 21st 2015, 05:44 AM
  2. [Abstract Algebra] Anyone care to proof-read a proof?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Dec 4th 2012, 01:13 PM
  3. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  4. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum