Proof by Mathematical Induction for Inequality

Question

Prove, by mathematical induction, that $$\sum_{i=1}^n\frac{i}{i+1}\leq \frac{n^2}{n+1}$$ (When $n$ is a natural number.)

So I went through all the typical steps you'd go through with mathematical induction, and after assuming that the statement at $n+1$ was true, I ended up with the following:

$$\sum_{i=1}^{n+1}\frac{i}{i+1}\leq \frac{(n+1)^2}{n+2}$$ ... (algebra) ... $$\sum_{i=1}^n\frac{i}{i+1}\leq \frac{n^2+n}{n+2}$$

But since the right hand side of the inequality I ended up with is greater than the original right hand side of the inequality I wanted to end up with, this doesn't help me prove the original statement. So I've either done something wrong with my algebra or I'm not thinking far enough outside the box; how do I use induction to prove this?

Answer 1

Suppose that $\sum_{i=1}^{i=n}{i\over{i+1}}\leq {n^2\over{n+1}}$,

$\sum_{i=1}^{i=n+1}{i\over{i+1}}\leq {n^2\over{n+1}}+{{n+1}\over{n+2}}$.

${n^2\over{n+1}}+{{n+1}\over{n+2}}=$

${{n^2(n+2)+(n+1)^2}\over{{(n+1)(n+2)}}}$

$\leq {{n(n^2+2n+1)+(n+1)^2}\over{{(n+1)(n+2)}}}$

$={{n(n+1)^2+(n+1)^2}\over{(n+1)(n+2)}}={{(n+1)^2}\over{n+2}}$.

Answer 2

I think you're doing induction backwards; if you assume $n+1$ is true you're already done the inductive step. Assume $n$ is true, that is: $$\sum_{i=1}^n\frac{i}{i+1}\leq \frac{n^2}{n+1}$$ and try to prove that $$\sum_{i=1}^{n+1}\frac{i}{i+1}\leq \frac{(n+1)^2}{n+2}$$

Answer 3

The base case $n=1$ is clear.

For the induction case, start with what you know is true, whch is the statement for $n$ : $\sum_{i=1}^n \frac{i}{i+1} \leq \frac{n^2}{n+1}$. If we show that each time the left hand side's increase is slower than the right hand side then we are done.

When we put $n+1$ in place of $n$, the left hand side increases by $\frac{n+1}{n+2} = 1 - \frac{1}{n+2}$. The right hand side, on the other hand, increases by $\frac{(n+1)^2}{n+2} - \frac {n^2}{n+1} = 1-\frac{1}{(n+1)(n+2)}$.

Now, clearly, $\frac{1}{n+2} > \frac{1}{(n+1)(n+2)}$. Therefore, the right hand side has increased more than the left hand side. Adding this to the inequality given by the case for $n$ gives you the proof.