Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Which one is bigger $2^{n!}$ or $(2^{n})!$?

where n∈N.

share|improve this question
2  
Hint: Take logarithms, and exploit the Stirling asymptotic formula. –  J. M. Aug 27 '10 at 10:15
3  
small n, large n, or any $n\in\mathbb{N}$? –  Tobias Kienzler Aug 27 '10 at 10:18
2  
Why are you interested in this? What is your motivation? –  Rasmus Aug 27 '10 at 11:22
2  
@Rasmus These two things popped up in my mind from nowhere. I was just wondering which one is bigger. Call it recreational mathematics if you like :) –  Pratik Deoghare Aug 27 '10 at 11:30
    
What can we say about f(g(n)) relative to g(f(n)) in general? –  Jules Oct 25 '11 at 14:09
add comment

6 Answers

up vote 22 down vote accepted

We should expect $2^{n!}$ be larger. Note that $(2^n)! \leq (2^n)^{(2^n)} = 2^{(n 2^n)}$. So we want to prove $n 2^n < n!$ eventually. (And this can be done very simply.)

share|improve this answer
1  
Very nice! The "very simple effort" establishes the inequality for n >= 6. The cases n = 0, ..., 5 are quick checks (and for some of them the inequality is reversed, as Tobias Kienzler notes). That completely addresses the problem. –  whuber Aug 27 '10 at 14:43
add comment

It's enough to take this limit: $\lim_{n \rightarrow \infty} \frac{2^{n!}}{(2^n)!}$, by the Stirling formula we get $\lim_{n \rightarrow \infty} \frac{2^{(\frac{n}{e})^n \sqrt{2 \pi n}}}{(\frac{2^n}{e})^{2^n} \sqrt{2 \pi 2^n}}$, which is asymptotic (after elevating and taking logarithms) to $\lim_{n \rightarrow \infty} \frac{\exp(\frac{n^n}{e^n})}{\exp(2^n 2^{n/2})} = \lim_{n \rightarrow \infty} \frac{\exp(\frac{n^n}{e^n})}{\exp(2^{3/2 n})}$. Now, $\frac{n^n}{e^n}$ is bigger than $2^{3/2n}$ (and it is easy to verify). So the limit is infinite, which means that $2^{n!}$ is bigger than $(2^n)!$, if $n$ is big, of course.

Little note: I know that the asymptotic preseves constants and, even though I omitted them, it's good practice always to include them.

share|improve this answer
1  
"exponential function is always bigger than the factorial one."? How come the series for the exponential function converges, then? –  J. M. Aug 27 '10 at 10:55
    
It is a good general rule that the exponential function is always bigger than the factorial one. Really? The Stirling formula says other things. –  Dario Aug 27 '10 at 10:56
    
Yeah, I'll edit, I was thinking of $n^n$ as "exponential", but that's because my professors addressed it that way (it was a bit confusing) –  Andy Aug 27 '10 at 10:57
add comment

Actually, $(2^n)!$ is larger if 1 < n < 4.97399743597. See this graph for detail.

share|improve this answer
    
What an estimate! –  anonymous Aug 27 '10 at 15:37
add comment

By proceeding straightforwardly we can answer without using Stirling's formula. To start we show that $(n-1)!>2^n$ for large n. [by induction] First note that $5!>2^6$. Then we note that if we increase n by 1 we multiply the left hand side by n, and the right hand side by 2. Since n>2 we conclude that the left hand side remains larger for bigger and bigger n.

Multiplying by n we get $n!>n2^n$ Replacing n with $log(2^{n})$ [using base-2 logarithms] gets us: $n!>2^{n}log(2^{n})$ Note that $2^{n}log(2^{n})$= $log(2^{n})$+$log(2^{n})$+$log(2^{n})$+...$log(2^{n})$+$log(2^{n})$

[$2^n$ terms]

$>log(2^{n})$+$log(2^{n}-1)$+$log(2^{n}-2)$+...log(2)+log(1)

[since this has the same amount of terms, and some of them are smaller.]

=$log(2^{n}!)$ [combining logs]

Putting together these inequalities gives us that n!>$log(2^{n!})$, and raising 2 to these powers gives $2^{n!}$>$(2^{n}!)$ [for n>5 since our induction only told us that $(n-1)!>2^n$ for n>5]

share|improve this answer
    
Where does your $n>2$ originate from? What about Kenny's statement or my simple number example? –  Tobias Kienzler Aug 27 '10 at 11:14
1  
Well the induction base case is n=6, so were working upward from there. I'll edit to make it clear that this only works for n>5 –  Oscar Cunningham Aug 27 '10 at 11:21
    
This appears to be a round-about way of reproducing yjj's earlier demonstration. –  whuber Aug 27 '10 at 16:13
    
Yes, yjj's phrasing is much more succinct. (NB it wasn't earlier though.) –  Oscar Cunningham Aug 28 '10 at 10:17
add comment

Indefinite:

for $n=0$: $2^{0!}=2^1=2,$ $(2^0)!=1!=1$, so $2^{0!}>(2^0)!$

for $n=2$: $2^{2!}=2^2=4,$ $(2^2)!=4!=12$, so $2^{2!}<(2^2)!$.

share|improve this answer
3  
That's correct but uninteresting. The question implicitly asks us to characterize when (i.e., for which n) one side is larger than the other. –  whuber Aug 27 '10 at 14:32
add comment

$ 2^{n!}=(2^n)^{(n-1)!} $, so we have to compare $(2^n)^{(n-1)!} $ and $ (2^n)! $. For $n\geq 6$, $(n-1)!>2^n$. I may be wrong, but doesn't the result follow immediately from this? It's still true for $n=5$ though, but not for $n=4$.

share|improve this answer
    
You seem to have independently reproduced yjj's earlier response. –  whuber Aug 27 '10 at 16:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.