2
$\begingroup$

I've been stuck on this proof for a long time. I don't even really know where to start.

I've tried simplifying the inequality to:

$$\frac{n^n}{3^{n-1}} \leq n!.$$

But I couldn't find any leads to follow there. Could someone give me a hint on where to go from here. I'm just so lost. Any help would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Induction on $n$ works like a charm, using the elementary upper bound $\left(1+\frac1n\right)^n\leqslant3$ for every $n\geqslant1$. $\endgroup$ – Did Mar 9 '18 at 7:40
  • 1
    $\begingroup$ Interestingly, rather than following the hint in the comment above or digesting the correct answer below, you quasi instantly accepted the flagrantly false "answer" you had just received. Did you at least check it? Already its first line is wrong. (Please note that regulars of the site are not surprised that it is, coming from this user.) $\endgroup$ – Did Mar 9 '18 at 7:52
  • $\begingroup$ Boy I'm really messing up everything tonight. I should have looked at that answer more carefully. That's my fault, I need to be better about properly understanding the answers. I won't let this happen again. $\endgroup$ – user508828 Mar 9 '18 at 7:56
  • $\begingroup$ It is 9 am here, good morning :P $\endgroup$ – Paolo Leonetti Mar 9 '18 at 7:57
  • $\begingroup$ Good morning to you, thank you for your answer to my question. I really appreciate everyone's help. $\endgroup$ – user508828 Mar 9 '18 at 7:58
1
$\begingroup$

Fix $n=3k \ge 3$ (the other cases can be done similarly), then \begin{align} n!=(3k)!&\ge (3k)(3k-1) \cdots (k) \\ &= (2k)\prod_{i=1}^k (2k+i)(2k-i)\\ &\ge (2k)\prod_{i=1}^k (2k+k)(2k-k)\\ &=(2k)(3k^2)^k \\ &= (2\cdot 3^k) k^{3k}\\ & \ge (2\cdot 3) k^{3k} \\ &>3 \left(\frac{n}{3}\right)^n. \end{align}

$\endgroup$
  • $\begingroup$ Some terms in the product in the first line could be non-integer. Is this certainly not a problem? $\endgroup$ – Alex Mar 9 '18 at 8:11
  • $\begingroup$ @Alex With "the other cases", I was referring to "non-multiples of $3$".. $\endgroup$ – Paolo Leonetti Mar 9 '18 at 8:12
  • $\begingroup$ I got it. So there's no single solution, i.e. for all $n$. $\endgroup$ – Alex Mar 9 '18 at 8:16
  • 1
    $\begingroup$ Not as it is. But minor modifications work with noninteger $k$: note that $$\frac{f(n+1)}{f(n)}\le \frac{f(n+2)}{f(n)}<2n$$ for all $n$, where $f(n):=(\frac{n}{3})^n$. Then, setting $k=\lfloor n/3\rfloor$, $$ n! \ge (3k!) \ge (2\cdot 3^k) k^{3k} (k-1)! \ge 9k\cdot k^{3k} \ge f(n). $$ $\endgroup$ – Paolo Leonetti Mar 9 '18 at 8:25
  • $\begingroup$ ah good one, thanks @Paolo $\endgroup$ – Alex Mar 9 '18 at 11:55

Your Answer

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