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

Question

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!

Answer 1

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

Answer 2

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.

Answer 3

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.