Prove that $(1+\frac{1}{n})^k < 1+ \frac{k}{n}+\frac{k^2}{n^2}$ Prove that $(1+\frac{1}{n})^k < 1+ \frac{k}{n}+\frac{k^2}{n^2}, \forall$ n, k nonnegative integers, $k\le n$.
I know that has something to do with Bernoulli's inequality $(1+\alpha)^x\ge 1+\alpha x, \alpha \ge -1, n\ge1$.
If I reconsider Bernoulli's inequality with $\alpha=\frac{1}{n}$ and $x=k$ it follows that
$(1+\frac{1}{n})^k\ge 1+\frac{k}{n}$, but I don't know how to continue.
I also tried to prove it with induction where I consider
$p(n):(1+\frac{1}{n})^k < 1+ \frac{k}{n}+\frac{k^2}{n^2}$ to be true and prove that $ p(n+1):(1+\frac{1}{n+1})^k < 1+ \frac{k}{n+1}+\frac{k^2}{(n+1)^2}$ to be also true, but it didn't work.
Thank you!
 A: Fix $n\in\Bbb N$. The claim is trivial in the case $k=1$, so by induction assume the claim is true for some $k<n$. Then we get:
\begin{align*}
\left(1+\frac{1}{n}\right)^{k+1}&<\left(1+\frac{k}{n}+\frac{k^2}{n^2}\right)\left(1+\frac{1}{n}\right)\\
&=1+\frac{k}{n}+\frac{k^2}{n^2}+\frac{1}{n}+\frac{k}{n^2}+\frac{k^2}{n^3}\\
&\overset{k<n}{<}1+\frac{k+1}{n}+\frac{k^2+k}{n^2}+\frac{nk}{n^3}\\
&=1+\frac{k+1}{n}+\frac{k^2+2k}{n^2}\\
&<1+{\frac{k+1}{n}}+\frac{k^2+2k+1}{n^2}\\
&=1+\frac{k+1}{n}+\frac{(k+1)^2}{n^2}
\end{align*}
which proves the claim the case $k+1\leq n$. (Actually we see from this proof that the statement is also correct for $k=n+1$.)
A: As a hint: exp(x) = 1 + x + x^2/2 + x^3/6 ... The right hand side is 1 + x + x^2, cutting the series short, but not dividing the quadratic term by 2. So for small k not dividing the quadratic term on the right side will make it larger for small k, but for large k adding the missing terms on the left side makes it larger. Try with n = 1 and k = 1, 2, 3, etc.
I’d write down all the terms for fixed n and a given k on the left side, and show that the higher powers are less than the extra k^2/2n^2 on the right hand side, as long as k isn’t too large.
A: Proof without induction/calculus:
It's easy to prove the inequality is true for $k=1,2$. If $k\ge 3$ we have
$$\left(1+\frac{1}{n}\right)^k - 1- \frac{k}{n}-\frac{k^2}{n^2} $$ $$= - \frac{k^2}{n^2} + \binom{k}{2} \frac{1}{n^2} + \sum_{i=3}^k \binom{k}{i} \frac{1}{n^i} = -\frac{k(k+1)}{2n^2}+\sum_{i=3}^k \binom{k}{i} \frac{1}{n^i} \tag1$$
Notice that
$$\frac{\binom{k}{i+1}/n^{i+1}}{\binom{k}{i}/n^i}=\frac{k-i}{n(i+1)} \le \frac{k-3}{4n}, \forall i \ge 3$$
Then $(1)$ is less then
$$-\frac{k(k+1)}{2n^2} + \frac{\binom{k}{3}/n^3}{1-\frac{k-3}{4n}}$$ and it suffices to prove
$$ \frac{\frac{k(k-1)(k-2)}{6n^3}}{1-\frac{k-3}{4n}} < \frac{k(k+1)}{2n^2}$$
Or equivalently
$$\frac{4(k-1)(k-2)}{4n-k+3} < 3(k+1) \iff 4(k-1)(k-2) < 3(k+1)(4n-k+3)\\
\stackrel{k\le n}{\Leftarrow} 4(k-1)(k-2) < 3(k+1)(4k-k+3) = 9(k+1)^2$$ which is trivially true.
