• Support PF! Buy your school textbooks, materials and every day products Here!

Function Growth Rates

  • Thread starter Klion
  • Start date
  • #1
14
0
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
 

Answers and Replies

  • #2
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.
 
Last edited by a moderator:
  • #3
14
0
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:
  • #4
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 :\
 
Last edited by a moderator:
  • #5
14
0
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.
 
  • #6
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.
 
Last edited by a moderator:
  • #7
14
0
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 :)
 
  • #8
vsage
Klion said:
le hospital's rule
BTW I used to annoy the heck out of my calc professor saying that :) Sorry I couldn't help much.
 

Related Threads for: Function Growth Rates

  • Last Post
Replies
9
Views
601
Replies
2
Views
8K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
3
Views
14K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
1K
Top