8
$\begingroup$

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

where $n\in\mathbb N$.

  • 2
    Hint: Take logarithms, and exploit the Stirling asymptotic formula.2010-08-27
  • 3
    small n, large n, or any $n\in\mathbb{N}$?2010-08-27
  • 2
    Why are you interested in this? What is your motivation?2010-08-27
  • 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 :)2010-08-27
  • 0
    What can we say about f(g(n)) relative to g(f(n)) in general?2011-10-25

6 Answers 6

25

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

  • 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.2010-08-27
4

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.

  • 1
    "exponential function is always bigger than the factorial one."? How come the series for the exponential function converges, then?2010-08-27
  • 0
    *It is a good general rule that the exponential function is always bigger than the factorial one.* Really? The Stirling formula says other things.2010-08-27
  • 0
    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)2010-08-27
4

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

  • 0
    What an estimate!2010-08-27
4

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]

  • 0
    Where does your $n>2$ originate from? What about [Kenny's statement](http://math.stackexchange.com/questions/3452/which-one-is-bigger-2n-or-2n/3456#3456) or [my simple number example](http://math.stackexchange.com/questions/3452/which-one-is-bigger-2n-or-2n/3453#3453)?2010-08-27
  • 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>52010-08-27
  • 0
    This appears to be a round-about way of reproducing yjj's earlier demonstration.2010-08-27
  • 0
    Yes, yjj's phrasing is much more succinct. (NB it wasn't earlier though.)2010-08-28
1

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

  • 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.2010-08-27
1

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

  • 0
    You seem to have independently reproduced yjj's earlier response.2010-08-27