prove that n! = O(n^n)

问题:

Update: Sorry I forgot to put n^n inside the O()

My attempt was to solve this recurrence relation:

T(n) = nT(n-1) +1
T(0) = 1;

Using the iteration method I got the n^n but Im not sure if this is the way to prove it.

回答1:

I assume that you want to prove that the function n! is an element of the set O(n^n). This can be proven quite easily:

Definition: A function f(n) is element of the set O(g(n)) if there exists a c>0 such that there exists a m such that for all k>m we have that f(k)<=c*g(k).

So, we have to compare n! against n^n. Let's write them one under another:

n!  = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
n^n = n *  n    *  n    *  n    * ... * n * n * n

As you can see, the first line (n!) and the second line (n^n) have both exactly n items on the right side. If we compare these items, we see that every item is at most as large as it's corresponding item in the second line. Thus n! <= n^n (at least for n>5).

So, we can - look at the definition - say, that there exists c=1 such that there exists m=5 such that for all k>5 we have that k! < k^k, which proves that n! is indeed an element of O(n^n).

回答2:

Remark: The following is an answer to the original Question which was: "Prove that n! = n^n"

I can prove that it's not true pretty easily: take n = 5.

n! = 120
n^n = 3125

回答3:

It is not true that n! = n^n, and therefore you will not be able to prove that. Furthermore, the solution to your recurrence relation is neither n! or n^n. (It satisfies T(1) = 1*1+1 = 2, which is neither 1! nor 1^1.)

What exactly are you trying to do, and why?

回答4:

n! != n^n. However, the T(n) sequence defined above is not n!. But does it equal n^n? For n=1, T(1) = 1*T(0) + 1 = 1*1 + 1 = 2 but n^n = 1^1 = 1. However, assuming you also meant T(1) = 1, then they're equal for n=1. Going a step further, for n=2, then T(2) = 2*T(1) + 1 = 2*1 + 1 = 3 != 2^2. So I'm honestly not sure what you're trying to ask.

回答5:

for n==2, n! = 2 != 4 = n^n.
for n!=2, (n-1) divides n! but n-1 does not divide n^n (n^n mod n-1 == 1)

The actual stirling approximation is n! ~ sqrt(2 Pi n) (n/e)^n

What is your mathematical background? Do you want a complex analytic proof or something more combinatorial in nature?