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.
 A: 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.
A: $\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.$$
A: This is equivalent to proving
$$P(n)\colon\qquad (n+1)^n <n^{n+1}$$
for $n\ge3$.
Inductive step: We assume that $P(k-1)$ holds, i.e., that
$$k^{k-1}<(k-1)^k.$$
We will prove $P(k)$ by contradiction.
Assume that $P(k)$ does not hold, i.e.,
$$(k+1)^k \ge k^{k+1}.$$
By multiplying the inequalities
$$
\begin{align*}
(k-1)^k &> k^{k-1}\\
(k+1)^k &\ge k^{k+1}
\end{align*}
$$
we get
$$(k^2-1)^k \ge k^{2k},$$
i.e., $(k^2-1)^k \ge (k^2)^k$, which is a contradiction.

This can be used to show that the sequence $\sqrt[n]{n}$ is eventually decreasing. I guess there are a few posts about this question, but I was not able to find some such post quickly.
A: Two approaches

Bernoulli-like Inductive Step
$$
\begin{align}
\frac{\left(1+\frac1{n+1}\right)^{n+1}}{\left(1+\frac1n\right)^n}
&=\overbrace{\left(\frac{n(n+2)}{(n+1)^2}\right)^{n+1}}^{\lt1}\frac{n+1}n\\
&\lt\frac{n+1}n
\end{align}
$$
This shows that if $\left(1+\frac1n\right)^n\lt n$, then $\left(1+\frac1{n+1}\right)^{n+1}\lt n+1$

Non-Inductive Bernoulli Approach
Bernoulli's Inequality says that for $n\ge2$,
$$
\begin{align}
\left(1-\frac1{n+1}\right)^n
&=\left(\left(1-\frac1{n+1}\right)^{n/2}\right)^2\\
&\ge\left(1-\frac{n/2}{n+1}\right)^2\\[3pt]
&=\left(\frac{n/2+1}{n+1}\right)^2
\end{align}
$$
which is the reciprocal of
$$
\begin{align}
\left(1+\frac1n\right)^n
&\le\left(\frac{n+1}{n/2+1}\right)^2\\[6pt]
&\lt2^2
\end{align}
$$
Thus, $\left(1+\frac1n\right)^n\lt n$ if $n\ge4$.
We just need to verify the inequality for $n=3$:
$$
\left(1+\frac13\right)^3=\frac{64}{27}\lt3
$$
