• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter dzza
  • Start date
  • #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?
 

Answers and Replies

  • #2
hunt_mat
Homework Helper
1,741
25
Here is something which may help:
[tex]
\left(\frac{n}{n+1}\right)^{n}=\left(1-\frac{1}{n+1}\right)^{n}
[/tex]

You also know that:

[tex]
\left(1-\frac{1}{n+1}\right)^{n+1}<\frac{1}{e}<\frac{1}{2}
[/tex]

Play around and see what you get.
 

Related Threads on Induction to show n!/(n^n) is less than .5^k

Replies
6
Views
1K
Replies
4
Views
3K
  • Last Post
Replies
5
Views
1K
Replies
4
Views
1K
Replies
7
Views
6K
Replies
4
Views
9K
  • Last Post
Replies
5
Views
915
Replies
12
Views
5K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
4
Views
1K
Top