Induction to show n/(n^n) is less than .5^k

[dzza]

Homework Statement

Show that \frac{n!}{n^n} \leq \frac{1}{2}^k for all n \geq 2, where k is the greatest integer less than or equal to n/2.

Homework Equations

Mathematical Induction

The Attempt at a Solution

I've shown the base case, and I've assumed that the hypothesis is true for the induction step.
Now I want to show it is true for

\frac{(n+1)!}{(n+1)^(n+1)} \leq (\frac{1}{2})^k where k is now the greatest integer less than or equal to (n+1)/2

Currently I have the LHS looking like this:

(\frac{n!}{n^n})\cdot (\frac{n}{n+1})^n

The first term is the term from the induction hypothesis, which is good. But I'm lost on where to go with the second term. To obtain the RHS, I need only show that this term is less than a half. It is clear to me that

(\frac{n}{n+1})^n

is a decreasing sequence bounded above by 1/2. But how can I actually rigorously show this? I tried to show it was strictly decreasing by induction (so that I could show the n=2 case was an upper bound), but the terms were unnecessarily complicated and it didn't pan out.

Any suggestions?

 

[hunt_mat]

Here is something which may help:
<br /> \left(\frac{n}{n+1}\right)^{n}=\left(1-\frac{1}{n+1}\right)^{n}<br />

You also know that:

<br /> \left(1-\frac{1}{n+1}\right)^{n+1}&lt;\frac{1}{e}&lt;\frac{1}{2}<br />

Play around and see what you get.