# Prove that $(1+\frac{1}{n})^k < 1+ \frac{k}{n}+\frac{k^2}{n^2}$ [duplicate]

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!

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. 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 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$$.)

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.

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.