Prove by Induction that $n! > \left(\frac{n}{e}\right)^n$ for $n>1$

Question

I'm studying a combinatorics text (Cameron) in preparation for taking discrete math this upcoming semester. I've taken a fair amount of math in college, through Calculus II, but this is my first 500+ level math course.

Here is the problem that I'm stuck on. It appears after an introduction to Induction proofs.

Prove by Induction that:

$$n! > \left(\frac{n}{e}\right)^n$$

for $n>1$.

The book gives a hint: may use the fact that $\left(1 + \frac{1}{n}\right)^n < e$ for all n.

I have the base step:

$$P(1): 1! > \left(\frac{1}{e}\right)^1$$ $$1 > 0.37$$

For the inductive step, assume:

$$P(k): k! > \left(\frac{k}{e}\right)^k$$

and prove:

$$(k + 1)! > \left(\frac{k+1}{e}\right)^{k + 1}$$

Answer 1

Notice that

$$(k+1)!=(k+1)k!>(k+1)\left(\frac ke\right)^k>\frac{k+1}e\left(\frac{k+1}e\right)^k=\left(\frac{k+1}e\right)^{k+1}$$

The last inequality step uses the fact that

$$k^k>\frac{(k+1)^k}e$$

or,

$$e>\frac{(k+1)^k}{k^k}=\left(1+\frac1k\right)^k$$

Answer 2

Hint: $$\dfrac{\left(\dfrac{k+1}{e}\right)^{k+1}}{\left(\dfrac{k}{e}\right)^{k}}=\dfrac{k+1}{e}\left(\dfrac{k+1}{k}\right)^k=\dfrac{k+1}{e}\left(1+\dfrac{1}{k}\right)^k$$ while $$\dfrac{(k+1)!}{k!}=k+1$$

Answer 3

Hint. Start be re-expressing the right hand side for $k+1$ to get $$\Bigl(\frac{k+1}{e}\Bigr)^{k+1} =\frac{k+1}{e}\Bigl(\frac{k+1}{k}\Bigr)^k\Bigl(\frac ke\Bigr)^k =\frac{k+1}{e}\Bigl(1+\frac{1}{k}\Bigr)^k\Bigl(\frac ke\Bigr)^k\ .$$ Now use the hint you were given, and the inductive assumption.

Answer 4

For the proof by induction, assume that $$k!>\left(\frac{k}{e}\right)^k$$ and show that this implies $$(k+1)!>\left(\frac{k+1}{e}\right)^{k+1}$$ you can express this inequality as: $$(k+1)k!>\left(\frac{k+1}{e}\right)\left(\frac{k+1}{e}\right)^k$$ divide by $(k+1)$: $$k!>\left(\frac{1}{e}\right)\left(\frac{k+1}{e}\right)^k$$ When this is combined with the initial assumption, it's apparent that proving the following inequality to be true will complete the proof by induction: $$\left(\frac{k}{e}\right)^k>\left(\frac{1}{e}\right)\left(\frac{k+1}{e}\right)^k$$ refactor: $$\frac{k^k}{e^k}>\frac{(k+1)^k}{e^{k+1}}$$ rearrange: $$e>\left(\frac{k+1}{k}\right)^k=\left(1+\frac{1}{k}\right)^k$$ This last inequality is already given by your hint, so the proof is complete.