# Math Help - Proof by Induction

1. ## Proof by Induction

Prove by induction that n! > (n/3)^n

2. Sorry, I made a mistake: the following doesn't help much.

Originally Posted by h2osprey
Prove by induction that n! > (n/3)^n
n = 1:

1! = 1 > (1/3)^1

n -> n+1

$(n+1)! = (n+1)*n! > (n+1)(n/3)^n > n (n/3)^n > n/3 * (n/3)^n = (n/3)^{n+1}$

3. Originally Posted by Rapha
n = 1:

1! = 1 > (1/3)^1

n -> n+1

$(n+1)! = (n+1)*n! > (n+1)(n/3)^n > n (n/3)^n > n/3 * (n/3)^n = (n/3)^{n+1}$
Shouldn't it be $((n+1)/3)^{n+1}$?

4. Originally Posted by h2osprey

Prove by induction that n! > (n/3)^n
to complete your induction use the identity: $(n+1) \left(\frac{n}{3} \right)^n=\frac{3}{(1+\frac{1}{n})^n}\left(\frac{n +1}{3} \right)^{n+1}$ and this fact that: $\left(1+ \frac{1}{n} \right)^n < e < 3.$

note that the solution is actually suggesting a stronger inequality, i.e. $\forall n \in \mathbb{N}: \ n! > \left(\frac{n}{e} \right)^n.$

5. Here is a non-induction proof:
$e^n = \sum_{k=0}^{\infty} \frac{n^k}{k!} > \frac{n^n}{n!}$