Let $k \geq 6$ and I know $k!$ < $\dfrac{k^k}{2^k}$ I want to show the following:

$(k+1)! < \dfrac{(k+1)^{k+1}}{2^{k+1}}$

Now I am going to show my solution, let me know if my reasoning is correct as well.

Simplifying what we have above we get: $(k+1)k!$ < $\dfrac{(k+1)(k+1)^k}{2^{k+1}}$

Now divide $(k+1)$ from both sides: $k!$ < $\dfrac{(k+1)^k}{2^{k+1}}$

Next, factor out a k from the right side: $k!$ < $\dfrac{k^k(1+ \frac{1}{k})^k}{2^{k+1}}$

Now we know $\lim_{k\to\infty}$ $(1+ \frac{1}{k})^k$ is $e$ so we can write:

$k!$ < $\dfrac{k^ke}{2^{k+1}}$ $\iff$ $k!$ < $\dfrac{k^ke}{2\cdot2^k}$

This is also equivalent to: $k!$ < $\dfrac{k^k}{2^k}$ $\cdot$ $\dfrac{e}{2}$

Since I know $k!$ < $\dfrac{k^k}{2^k}$ (from an induction hypothesis) and I am multiplying by $\dfrac{e}{2}$ which is > $1$ the inequality holds. End of Proof.

The step I am most unsure of is setting the $(1+ \frac{1}{k})^k$ to $e$. Can I do this?

  • $\begingroup$ No you can't. But you can probably easily show that $(1+1/k)^k\gt 2$. Then rewrite the proof so that you are not going backwards. $\endgroup$ – André Nicolas Sep 21 '12 at 2:14
  • $\begingroup$ Could you give me a hint about how to show that that statement is true? I have no idea. $\endgroup$ – CodeKingPlusPlus Sep 21 '12 at 2:29
  • $\begingroup$ Where does the $\dfrac{k(k-1)}{2}$ in front of $x^2$ come from? Shouldn't it be in front of $x$? And also in your example we get $\dfrac{3}{2}$ $\endgroup$ – CodeKingPlusPlus Sep 21 '12 at 5:07
  • $\begingroup$ Sorry, typo. For $k\ge 2$, $(1+x)^k\ge 1+kx+\frac{k(k-1)}{2}x^2$. (Shouldn't try to type math in comments.) Put $x=1/k$. The first two terms give 1+k(1/k)=2$, the next adds to it. Actually, you only need $\ge 2$, so $x^2$ term not needed. $\endgroup$ – André Nicolas Sep 21 '12 at 5:25

You can use the inequality $$ \left(1 + \frac{1}{n}\right)^n < e < \left(1 + \frac{1}{n}\right)^{n+1}. $$ (This can be proved using the Taylor series of $\log$.)


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.