<s>[INST] 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!
 [/INST] 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$.)
</s>