Which function has a higher growth rate: n! or 2^n?

[Klion]

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 want to use induction since I don't 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

 

[vsage]

"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.

 

[Klion]

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 couldn't 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

 

[vsage]

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 :\

 

[Klion]

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.

 

[vsage]

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.

 

[Klion]

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, thanks for help :)

 

[vsage]

le hospital's rule

BTW I used to annoy the heck out of my calc professor saying that :) Sorry I couldn't help much.