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,741
    Thanks
    568

    Re: Proof that A^n < N!

    For k > A^2 what happens to \frac{k!}{A^k} as 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,741
    Thanks
    568

    Re: Proof that A^n < N!

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

    \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 A > 1, the final expression above is clearly increasing without bound and so for all sufficiently large k it is greater than 1.

    You can do 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,106
    Thanks
    460

    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