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:
$$\left(\frac{n}{n+1}\right)^{n}=\left(1-\frac{1}{n+1}\right)^{n}$$

You also know that:

$$\left(1-\frac{1}{n+1}\right)^{n+1}<\frac{1}{e}<\frac{1}{2}$$

Play around and see what you get.