Math Induction Proof: $(1+\frac1n)^n < n$

So I have to prove:

For each natural number greater than or equal to 3, $$(1+\frac1n)^n<n$$

My work: Basis step: $n=3$ $$\left(1+\frac13\right)^3<3$$ $$\left(\frac43\right)^3<3$$ $$\left(\frac{64}{27}\right)<3$$ which is true.

Now the inductive step, assume $P(k)=\left(1+\frac1k\right)^k<k$ to be true and prove $P(k+1)=\left(1+\frac1{k+1}\right)^{k+1}<k+1$.

This is where I am stuck because usually you add or multiply by $k+1$ or some similar term.

Solution 1:

Hint: $$ \left( 1+\frac{1}{k+1} \right)^{k+1} = \left( 1 + \frac{1}{k+1}\right) \left( 1 + \frac{1}{k+1}\right)^{k} < \left( 1 + \frac{1}{k+1}\right) \left( 1 + \frac{1}{k}\right)^{k}\\ < \left( 1 + \frac{1}{k+1}\right)k $$ where the last inequality comes from your induction hypothesis.

Solution 2:

$\left(1+\frac 1 n\right)^n=1+1+\binom n 2\frac 1 {n^2}+\binom n 3 \frac 1 {n^3}+\dotsb+\frac 1 {n^n}$

But $\binom n k \frac 1 {n^k}=\frac {n(n-1)\dotsm(n-k+1)}{k!n^k}<\frac 1 {k!}$.

So the expression we're interested in is less than $$1+1+\frac 1 {2!}+\frac 1{3!}+\dotsb+\frac 1 {n!}<1+1+\frac 1 2 +\frac 1 4 +\frac 1 8+\dotsb=3.$$