0

I have to show the following by induction.

$1 \cdot 2 \cdot 3 ... (n - 1) \leq (\frac{n}{2})^{n -1}$

As it is homework I "only" need a push in the right direction. my thought is that is something to do with the binomial theorem.. but I'm pretty lost.

skyw00lker
  • 149
  • 1
    Assuming (inductive hypothesis) that $(n-1)! \leqslant \left(\frac{n}{2}\right)^{n-1}$, it is sufficient to show $$n\left(\frac{n}{2}\right)^{n-1} \leqslant \left(\frac{n+1}{2}\right)^n.$$ That may remind you of something. – Daniel Fischer Apr 16 '14 at 20:01
  • If I understand it correctly, how can you rewrite $(n -1)!$ as $\left(\frac{n}{2}\right)^{n-1}$ @DanielFischer I got it as soon as i asked! thanks! – skyw00lker Apr 16 '14 at 21:10

2 Answers2

1

\begin{align*} 1&\le\left(\frac12\right)^0\\ 1&\le1\\ 1\cdot2\cdot3\cdot\ldots\cdot(k-1)&\le\left(\frac k2\right)^{k-1}\\ k!&\le\left(\frac{k+1}2\right)^k\\ \left(\frac k2\right)^{k-1}k&\le\left(\frac{k+1}2\right)^k\\ 2\cdot k^k&\le(k+1)^k \end{align*}

Fourth row is what needs to be proven and 5, 6 are what is sufficient to prove. I guess you could take it from here.

user2345215
  • 16,422
kingW3
  • 13,496
0

This follows directly form the AM GM inequality.

Sandeep Silwal
  • 8,135
  • I don't get the downvotes $\frac n2=\frac{\frac{n(n-1)}2}{n-1}=\frac{1+\ldots+n-1}{n-1}\ge\sqrt[n-1]{1\cdot\ldots\cdot(n-1)}$ seems pretty direct. – user2345215 Apr 16 '14 at 20:14
  • Oh I get it, OP asked for an induction proof, but it's certainly more elegant than forcing an ugly AM-GM through induction instead instead of this nice one. – user2345215 Apr 16 '14 at 20:15
  • I did not down vote, thanks for the alternate solution, it was explicitly asked that it had to be done by induction, probably for the best with my lack of understanding! :) – skyw00lker Apr 16 '14 at 21:16