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

Question

$\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!

Answer 1

$$\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}$

Answer 2

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$

Answer 3

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.