Cdtjkyj

Prove by induction of n

$sumlimits_{k=1}^n frac k{k+1} leq n - frac1{n+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}

Now I'm a beginner at induction, and couldn't follow this solution very well.I was hoping someone could help break down the steps and explain them.

Questions

1. How the inequality works

Wouldn't

$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1} $

become

$sum_1^{n+1}frac k{k+1} +frac{n+1}{n+2} leq n-frac 1{n+1}$

and then

$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}-frac{n+1}{n+2} $

instead of

$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2} $

2. My largest issue with induction, is when the inequalities change like in the first and last step. I don't understand how that works. Any explanation, or good resources to help with my understanding of how the inequality changes when performing induction would be helpful.

Remember that in induction proofs, we start by assuming that the claim we're trying to prove is true for $n$, and then conclude that it must also be true for $n + 1$. In this case, we start with the induction assumption
$$sum_{k = 1}^{n} frac{k}{k + 1} leq n - frac{1}{n + 1},$$
and want to end with the conclusion that $$sum_{k = 1}^{n + 1} frac{k}{k + 1} leq n + 1 - frac{1}{n + 2} .$$
Here's the argument written out in a bit more detail with commentary on each step.
begin{align*}
sum_{k = 1}^{n + 1} frac{k}{k + 1} & = frac{n + 1}{n + 2} + sum_{k = 1}^{n} frac{k}{k + 1} & textrm{ (just writing out the sum)} \
& leq frac{n + 1}{n + 2} + n - frac{1}{n + 1} & textrm{ (applying the induction hypothesis)} \
& = 1 - frac{1}{n + 2} + n - frac{1}{n + 1} & textrm{ (rewriting $frac{n+ 1}{n + 2}$ as $frac{n + 2 - 1}{n + 2} = 1 - frac{1}{n + 2}$)} \
& = n + 1 - frac{1}{n + 1} - frac{1}{n + 2} & textrm{ (regrouping)} \
& = n + 1 - frac{(n + 2) + (n + 1)}{(n + 2)(n + 1)} & textrm{ (combining fractions)} \
& = n + 1 - frac{2(n + 2) - 1}{(n + 1)(n + 2)} & textrm{ (regrouping the numerator)} \
& = n + 1 - frac{2(n + 2)}{(n + 1)(n + 2)} + frac{1}{(n + 1)(n + 2)} & textrm{ (breaking the fraction back apart)} \
& = n + 1 - frac{2}{n + 1} + frac{1}{(n + 1)(n + 2)} & textrm{ (simplifying the fraction)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{(n + 1)(n + 2)} & textrm{ (we slightly modified the second-to-last summand)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{n + 2} & textrm{ (modifying the last summand)} \
& = n + 1 - frac{1}{n + 2} & textrm{ (combining the fractions)} .
end{align*}
So in summary, we began with the assumption that the claim held for $n$, and through some arithmetic trickery concluded that it therefore held for $n + 1$.

Regarding the first inequality you're asking about, they are actually adding the term $frac{n+1}{n+2}$ to both sides, but on the left hand side it is added by increasing the upper limit in the sum by $1$, and to not change the inequality you have to add $frac{n+1}{n+2}$ to the right hand side.

The subsequent steps in the proof you posted are just rearrangements of fractions using algebra, nothing actually changes there until the last line. Then they just use the fact that $frac{1}{(n+1)(n+2)} leq frac{1}{n+2}$

If $aleq b $, then $a+cleq b+c $ for any $cin Bbb R $. By assumption, we have $$sum_{k=1}^{n}frac k{k+1}leq n-frac 1{n+1}.$$ Now add $dfrac{n+1}{n+2}$ on both sides, i.e., $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$ Note that $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}=sum_{k=1}^{n+1}frac k{k+1}.$$ Hence we have $$sum_{k=1}^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$