# 5. Prove by induction on $n$ that $\sum\limits_{k=1}^n \frac k{k+1} \leq n - \frac1{n+1}$

$$\sum\limits_{k=1}^n \frac k{k+1} \leq n - \frac1{n+1}$$

Base Case:

I did $$n = 1$$, so..

LHS-

$$\sum \limits_{k=1}^n (k/(k+1)) = 1/(1+1) = 1/2$$

RHS-

$$n-(1/(n+1)) = 1 - (1/(1+1)) = 1/2$$

so LHS = RHS

Inductive case-

LHS for $$n+1$$

$$\sum \limits_{k=1}^n (k/(k+1)) + ((n+1)/(n+2))$$

and then I think that you can use inductive hypothesis to change it to the form of $$(n - (1/(n+1))) + ((n+1)/(n+2))$$ now form here I tried multiplying it out and solving with some algebra but I kept hitting dead ends. If you could explain your steps and the reasoning behind them I would appreciate it.

Edit-

Am i on the right track with the following solution for the inductive case? $$\sum \limits_{k=1}^n (k/(k+1)) = \sum \limits_{k=1}^n (n - (1/(n+1)) + (n+1)/(n+2)$$

then I think if i increase the denominator 1/(n+1) by 1 then it should become..

$${}< n - 1/(n+2) + (n+1/n+2)$$

$${}< n - 1/(n+2)$$

which is really close to the RHS of $$n+1$$ which is $$n+1 - 1/(n+2)$$... and since i did change the value of the denominator by 1 earlier, i feel like i should be able to add a 1 in now to make it equal. I'm not sure of the logic behind this though!

• If you are in the $n+1$ case, then the RHS should be $n + 1 - 1 / (n + 1 + 1)$ – DanielV Mar 2 at 6:37
• Anyway, check the $n=2$ case. – DanielV Mar 2 at 6:38
• How come you suggest to check n = 2? what lead you to that? – Brownie Mar 2 at 6:40
• Well that was before you changed it to an inequality – DanielV Mar 2 at 6:53
• Yea, sorry about that I realized that I had type the question wrong. You comment lead me to take another look at what I type. Does that change the process alot? – Brownie Mar 2 at 6:54

\begin{align}\sum_1^{n+1}\frac k{k+1}&\leq n-\frac 1{n+1}+\frac{n+1}{n+2}\\&=n-\frac 1{n+1}+1-\frac 1{n+2}\\&=(n+1)-\frac{2(n+2)-1}{(n+1)(n+2)}\\&=(n+1)-\frac 2{n+1}+\frac 1{(n+1)(n+2)}\\&\leq (n+1)-\frac 2{n+2}+\frac 1{n+2}=(n+1)-\frac 1{n+2}\end{align}

For the penultimate inequality, note that $$n+1\lt n+2$$, so $$-\frac 1{n+1}\lt -\frac 1{n+2}$$ and $$(n+1)(n+2)\gt (n+2)$$, so $$\frac 1{(n+1)(n+2)}\lt\frac 1{n+2}$$

• Could you explain the second step please? I'm having trouble following the solution, since i'm fairly new to this. If i'm understanding this right shouldn't at the top it be -(n+1)/(n+2) since you would subtract from the lhs and rhs side? – Brownie Mar 2 at 23:54
• @Brownie: it's just the inductive step: $$\sum_1^{n+1}\frac k{k+1}=\left(\sum_1^n\frac k{k+1}\right)+\frac{n+1}{n+2}\leq n-\frac 1{n+1}+\frac{n-1}{n-2}$$ where we apply the inductive hypothesis at the last step. – learner Mar 3 at 4:38

You are trying to prove that

$$\sum_{k = 1}^n \frac k {k+1} \le n - \frac{1}{n+1}$$

implies

$$\frac{n+1}{n+2} + \sum_{k = 1}^n \frac k {k+1} \le n+1 - \frac{1}{n+2}$$

So let $$A = \sum_{k = 1}^n \frac k {k+1}$$ $$B = n - \frac{1}{n+1}$$ $$C = n+1 - \frac{1}{n+2} - \frac{n+1}{n+2}$$

And use $$A \le B \text{ and } B \le C \text{ then } A \le C$$

It might be useful to rearrange the LHS of the inequality before proving it:

• $$\sum_{k=1}^n \frac k{k+1} = \sum_{k=1}^n \frac {k+1-1}{k+1} = \sum_{k=1}^n \left(1-\frac{1}{k+1} \right) = n - \sum_{k=1}^n \frac {1}{k+1}$$

Hence the inequality becomes $$\sum\limits_{k=1}^n \frac k{k+1} \leq n - \frac1{n+1} \Leftrightarrow n - \sum_{k=1}^n \frac {1}{k+1} \leq n - \frac1{n+1}$$ $$\Leftrightarrow \boxed{\sum_{k=1}^n \frac {1}{k+1} \geq \frac1{n+1}}$$

Now, there isn't much left to prove.

• This is a great solution, as a beginner its really easy for me to follow this! My one question is in your top line at the end, where you rearrange, what is the math behind you taking the 1 outside and it becomes n - the summation? – Brownie Mar 2 at 23:58
• @Brownie : This is so because of the definition of the sum symbol you have \begin{eqnarray*} \sum_{k=1}^n \left(1-\frac{1}{k+1} \right) & = &\underbrace{\left(1-\frac{1}{1+1} \right) + \cdots + \left(1-\frac{1}{n+1} \right)}_{n \: summands} \\ & = &\underbrace{\left(1+ \cdots +1 \right)}_{n\:summands} - \left(\frac{1}{1+1}+ \cdots +\frac{1}{n+1} \right) \\ & = & n - \sum_{k=1}^n \frac{1}{k+1} \end{eqnarray*} – trancelocation Mar 3 at 6:03