1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Function Growth Rates

  1. Sep 28, 2004 #1
    Alright problem is pretty simple, I have two functions

    f(x) = n!
    g(x) = 2^n

    Question is to show that g(x) = Of(x) through mathematical expression

    that is show the growth rate of g(x) <= that of f(x)

    The fact that this is true is fairly obvious, it's bigger for n>3.

    Anyway my problem is I only know how to define n! as a recursive definition, so I'm not really sure how to demonstrate this truth in any kind of mathematical way. If you put both as a reiman product or whatever it's called (ie n-i for i=0 to n and 2 for i=0 to n) you have a function compared to a number.


    2*2*2*2*....*2 (n terms)
    1*2*...*(n-1)*(n) (n terms)

    I don't really wanna use induction since I dont think it's necessary or expected, and I don't really know how to do the inductive step since one of the functions has no variables.

    Anyway any ideas? Or anyone know a non recursive definition for factorial so I can compare it to 2^n? heh
  2. jcsd
  3. Sep 29, 2004 #2
    "2*2*2*2*....*2 (n terms)
    1*2*...*(n-1)*(n) (n terms)"

    But don't both have variables? Consider a function h(x) = g(x)/f(x) = 2^x/x!

    isn't h(x+1) just h(x) * 2/(x+1) ? That would be your induction.. h(x+1)/h(x) obviously converges to 0 as x approaches infinity so you know that the denominator is growing faster than the numerator of h(x) as x gets very large.

    Edit: Sorry I don't know what level of class this is for so I don't know whether to make this proof look nicer or not. Tell me if this is not what you are looking for.
    Last edited by a moderator: Sep 29, 2004
  4. Sep 29, 2004 #3
    I meant 2^n doesn't have a variable when expressed as a reiman product or whatever.

    Well since I couldn't get a non-recursive definition of n! I couldnt do n!/2^n or 2^n/n!

    This is for a 200 level class, and I don't really think we're expected to do induction in it (at least not yet) though I could be mistaken.

    Anyway how do you figure

    "isn't h(x+1) just h( x) * 2/(x+1)" ?? boggle
    Last edited: Sep 29, 2004
  5. Sep 29, 2004 #4
    Oh so you're trying to do something with Riemann product notation? (pi?) Edit I see why you're saying there's no variable attached. Heh the only thing I can think of is that (n+1)! is (n+1)*pi(i, for i = 1 to n) and 2^(n+1) being 2 * pi(2, for i = 1 to n) but I don't get why this is such an impediment.

    Edit again: ok so I defined h(x) to be 2^x / x! right?

    h(x+1) can be expressed as h(x)*2/(x+1) because

    h(x)*2/(x+1) = 2^x/x! * 2/(x+1)

    = 2 * 2^x / (x! * (x+1))

    = 2^(x+1)/(x+1)!

    that h(x+1) = h(x) * 2/(x+1) would be sufficient to prove x! increases faster than 2^x but you keep indicating that induction is too complicated for the question and that there is a simpler way. Sorry I can't see one :\
    Last edited by a moderator: Sep 29, 2004
  6. Sep 29, 2004 #5
    Well I was trying that to remove the recursion problem but it didn't seem to help.

    I was just trying different types of math expression to try to show this silly thing is true, reimann product seemed best suited for factorials.

    I edited reply btw, but the part where you do

    h(x+1) just h( x) * 2/(x+1)

    .... you sure about that? boggle.
  7. Sep 29, 2004 #6
    Read edit :)

    Edit: I am very sure.

    Well look at it this way: If you can understand the induction and pull it off, it will establish you as more clever in the class. I really can't see any way other than induction for this.
    Last edited by a moderator: Sep 29, 2004
  8. Sep 29, 2004 #7
    Aha! Can do it with le hospital's rule. Friend just figured it out, cuz

    g(x) / f(x) = 2/n * 2/ (n-1) ... etc and as x approaches infinite 2/n = 0

    0x = 0 so g(x) / f(x) = 0 which means f(x) = og(x)

    woo. Annoying question mutter, thx for help :)
  9. Sep 29, 2004 #8
    BTW I used to annoy the heck out of my calc professor saying that :) Sorry I couldn't help much.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook