3
$\begingroup$

This is a generalization of this question :: Which is larger? $20!$ or $2^{40}$?.

No explicit general solution was presented there and I'm just curious :D

Thank-you.


Edit :: I want a most-general solution lfor arbitrary $x$ and $y$; not some specfic cases which can then be solved by direct computation. Below, Ahaan-Rungta shows that the case $x < y$ is the one to be considered.

$\endgroup$
2
  • 7
    $\begingroup$ Since $y!$ does not involve $x$, this question is not well posed. $\endgroup$
    – lhf
    Dec 16 '13 at 15:42
  • $\begingroup$ The solution may require some relation between $x$ and $y$ ---as I have no solution, I am unable to `pose' the question in a more suitable fashion. $\endgroup$ Dec 18 '13 at 11:42
8
$\begingroup$

For a fixed $x,$ $y!$ will eventually be larger, as you can tell by using Stirling's formula.

$\endgroup$
2
  • 1
    $\begingroup$ On the other hand, for a fixed $y$, as $x$ increases, $x^y$ will eventually be larger. It's really not clear from the question whether to keep $x$ fixed and let $y$ increase (as you do), or keep $y$ fixed and let $x$ increase (as I just did), or have them both increase in some way (in which case it matters exactly how they increase). $\endgroup$ Dec 17 '13 at 7:12
  • 1
    $\begingroup$ SreevatsaR :: yes; I am not choosing either constraint. I would a most-general solution. Thank-you. $\endgroup$ Dec 18 '13 at 11:44
4
$\begingroup$

Hint:

In general, for positive integer $x,y$ we have:

$y!=y(y-1)(y-2) \cdot\cdot\cdot2\cdot1$

$x^y=xxx\cdot\cdot\cdot xx$

  1. If $x\geq y$; then $ x^y\ge y! $
  2. If $x<y $, ?! (Now this is the question!)

Extra:

If $ \left\lceil{\frac{y}{2}}\right\rceil+1< x<y$; then $x^y\ge y!.$ (easy proof)

Now, we have only the case $ x\le\lceil{\frac{y}{2}}\rceil +1 $

$\endgroup$
3
$\begingroup$

"Just compute them and compare" is the only fully failsafe method.

In most cases, however, estimating the logarithms of both of $x^y$ and $y!$ using Stirling's formula will yield a conclusive result without needing to compute the two values in high detail.

$\endgroup$
4
  • 1
    $\begingroup$ Makkolm : As usually stated, Stirling's formula contains "big-O" notation that seems to make it useless to answer a specific problem with specific numbers such as the OP's. How can you remedy this? This is not a nitpick, I really want to know how to use Stirling's formula in problems like this. Where/how can one find guaranteed error bounds for the formula? $\endgroup$ Dec 17 '13 at 15:56
  • 1
    $\begingroup$ @Stefan: The Wikipedia article gives the error bound: $$1 \leq \frac{n!}{\sqrt{2\pi n} \left(\frac{n}{e}\right)^n} \leq \frac{e}{\sqrt{2\pi}} = 1.0844375514...$$ In other words, an absolute error bound for the logarithm of $n!$ is $1-\log \sqrt{2\pi} \approx 0.081$. $\endgroup$ Dec 17 '13 at 16:03
  • $\begingroup$ thanks, I spent a minute or so scanning the article and I did not see such a bound. $\endgroup$ Dec 17 '13 at 19:10
  • $\begingroup$ «"Just compute them and compare" is the only fully failsafe method.» Got a proof of that? $\endgroup$
    – Guido
    Apr 26 '18 at 16:08
1
$\begingroup$

$$\frac{20!}{2^{40}}= \frac{20!}{4^{20}} = \left(\frac{1}{4}\right)\left(\frac{2}{4}\right)\left(\frac{3}{4}\right) \left(\frac{4}{4}\right)\left(\frac{5}{4}\right)\left(\frac{6}{4}\right)\left(\frac{7}{4}\right)\left(\frac{8}{4}\right)\left(\frac{9}{4}\right)\cdots \left(\frac{20}{4}\right)>\cdots$$

$$ \left(\frac{1}{4}\right)\left(\frac{2}{4}\right)\left(\frac{3}{4}\right) \left(\frac{4}{4}\right)\left(\frac{5}{4}\right)\left(\frac{6}{4}\right)\left(\frac{7}{4}\right)\left(\frac{8}{4}\right)\left(\frac{9}{4}\right)=\frac{9!}{4^9}=\frac{2835}{2048}>1,$$

so $20!>2^{40}$.

$\endgroup$
3
  • $\begingroup$ Cool; now what about arbitrary $x$ and $y$? $\endgroup$ Dec 18 '13 at 11:45
  • 1
    $\begingroup$ That answer probably belongs to math.stackexchange.com/questions/562538/…. $\endgroup$
    – lhf
    Dec 18 '13 at 11:48
  • 1
    $\begingroup$ @Moses : the inequality Henning Makholm cites in his comment under his own answer to this question will work for many $x$ and $y$, but not all. $\endgroup$ Dec 19 '13 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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