Rate of growth of factorials.

[cp255]

I was wondering how fast x! grows as it approaches infinity as compared to x², 2^x, and x^x. The last one was fairly obvious since x*x*x*x... > x(x-1)(x-2)(x-3)... But I can't figure out a way to show that x! grows faster than x² or 2^x. I know it grows faster since I can compare the graphs of the functions on my calculator but I want to understand why. This since it seems like it would be helpful in solving limits where x approaches infinity, and using the comparison test for series which involve factorials.

 

[phyzguy]

Try looking up Stirling's formula.

 

[Stephen Tashi]

I haven't attempted the proofs you ask about, but my suggestions are these:

The error in Stirlings formula for approximating n! approaches infinity as n becomes large, but you can try to use the idea behind Stirlings formula.

For positive valued functions f and g, you can compare ln(f) and ln(g) to see which function is larger.

ln(n!) = ln( (n)(n-1)(n-2)...(1) ) = ln(n) + ln(n-1) + ln(n-2) + ...ln(1)

The latter sum is a Riemann sum that does a bad approximation for $\int_1^n \ln(x) dx$. It uses rectangles that have a base of 1. If you can prove the sum is an over-estimate of the integral then you can test if functions are smaller than the integral $\int_1^n {\ln(x)} dx = |_1^n (x \ln(x) - x)$

At least that gets rid of the factorial when you try to compare things.

The phrase "grows faster" is ambiguous. "f grows faster than g" might mean that f(n+1)-f(n) > g(n+1)-g(n) for n greater than some value k. Or it might mean f(n) > g(n) for n greater than some value k. No doubt there is a relation between these two statements, but you should clarify which you are tyring to prove.

 

[cp255]

I thought about it more and I realized that I was focusing on the end which starts at n and works backwards when really I should start at 1 and work forwards. For instance (assuming n is large enough which it can always be since we are talking about it approaching infinity) n! = 1 * 2 * 3 * 4 * 5 * ... * (n-1) * n. For the expression 2ⁿ or any other base the following continues n times. 2 * 2 * 2 * 2 * ... * 2. This starts out as the greater expression since it starts by multiplying by the base of the exponent whereas n! starts with 1 and works up incrementally. Eventually the value of the factors of n! will exceed 2 (or whatever the base of the exponent is) and begin increasing at a faster rate as compared to the exponential. Since n can become arbitrary large there will always be a point at which the factorial exceeds the exponential.

 

[HallsofIvy]

To compare $x^n$, $2^x$, and $x^x$ with x!. Look at the ratios.
$$\frac{x^n}{x!}$$
That fraction has a product of n "x"s in the numerator and numbers from 1 to x in the denominator. As soon as x is larger than n (which is fixed), the denominator will be much larger than the numerator. As x goes to infinity that fraction goes to 0.

$$\frac{a^x}{x!}$$
has x "a"s in the numerator and x numbers ranging from 1 to x in the denominator. You can think of that as a product of x fractions, each with "a" in the numerator and a number from 1 to x in the denominator. It should be clear that as soon as x> a, most of the numbers in the denominator will be larger than the numbers in the numerator and so the fraction is less than 1. As x goes to infinity, that product will go to 0.

$$\frac{x^x}{x!}$$
Now the numerator is a product of x "x"s while the denominator is a product from 1 to x. Again, we have the same number of terms in the numerator and denominator but now the numbers in the numerator are always large than or equal to the numbers in the numerator. If we think of this as the product of x fractions, one fraction is equal to 1 the others are all larger than 1. A x goes to infinity, the fraction goes to infinity.