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

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

where $n\in\mathbb N$.

-
Hint: Take logarithms, and exploit the Stirling asymptotic formula. –  Guess who it is. Aug 27 '10 at 10:15
small n, large n, or any $n\in\mathbb{N}$? –  Tobias Kienzler Aug 27 '10 at 10:18
Why are you interested in this? What is your motivation? –  Rasmus Aug 27 '10 at 11:22
@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

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

-
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

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.

-
"exponential function is always bigger than the factorial one."? How come the series for the exponential function converges, then? –  Guess who it is. 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

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

-
What an estimate! –  anonymous Aug 27 '10 at 15:37

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]

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

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)!$.

-
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

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

-
You seem to have independently reproduced yjj's earlier response. –  whuber Aug 27 '10 at 16:12