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.

    like

    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