- #1

- 14

- 0

## Homework Statement

Show that [tex]\frac{n!}{n^n} \leq \frac{1}{2}^k [/tex] for all [tex]n \geq 2[/tex], 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

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

Currently I have the LHS looking like this:

[tex](\frac{n!}{n^n})\cdot (\frac{n}{n+1})^n[/tex]

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

[tex](\frac{n}{n+1})^n[/tex]

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?