I am confused how you would continue with the inductive step. Thanks
Asked
Active
Viewed 76 times
2
-
Maybe after $n=5$ since it holds at $n=6$. – Juniven Acapulco Feb 08 '17 at 01:54
-
Yes, it should be after 5 or n >= 6 – JanoyCresva Feb 08 '17 at 02:04
-
3Hint: Observe that $({n+1\over{2}})^{n+1}=(\frac{n}{2}+\frac{1}{2})^{n+1}>(\frac{n}{2})^{n+1}+\frac{1}{2}(\frac{n}{2})^n$ – dave Feb 08 '17 at 02:07
1 Answers
2
Basis step, $P_6 : 6!<(\frac{6}{2})^6\rightarrow 720<3^6=729$. True
Inductive step, suppose $P_n$ is true, prove that $P_{n+1}$ is also true.
Note $P_n:n!<(\frac{n}{2})^n$ and $P_{n+1}:(n+1)!<(\frac{n+1}{2})^{n+1}$
Observe that, $$\begin{align}(\frac{n+1}{2})^{n+1}&=(\frac{n}{2}+\frac{1}{2})^{n+1} \\&>(\frac{n}{2})^{n+1}+(n+1)\cdot\frac{n^n}{2^{n+1}}+\frac{n(n+1)}{2}\cdot(\frac{n^{n-1}}{2^{n+1}})\tag{binomial}\\&=\frac{(5n+3)}{4}\cdot(\frac{n}{2})^n\\&=(n+\frac{n+3}{4})\cdot(\frac{n}{2})^n\\&>(n+1)\cdot(\frac{n}{2})^n,\forall n\ge6\end{align}$$
So, start with $P_n$,
$$\begin{align}n!(n+1)&<(\frac{n}{2})^n\cdot(n+1)\\&<(\frac{n+1}{2})^{n+1}\end{align}$$
MoNtiDeaD MoonDogs
- 752
- 3
- 11
-
-
Thank you for the help. I'm just confused with what you did on the (binomial) step – JanoyCresva Feb 08 '17 at 03:09
-
I edited again,
$\displaystyle (\frac{n}{2}+\frac{1}{2})^{n+1}=\binom{n+1}{0}(\frac{n}{2})^{n+1}+\binom{n+1}{1}(\frac{n}{2})^n\cdot\frac{1}{2}+...$
and I pick 1st, 2nd and 3rd terms.
– MoNtiDeaD MoonDogs Feb 08 '17 at 03:20