<s>[INST] The inductive proof of $\sum_{k=1}^n \frac k{k+1} \leq n - \frac1{n+1}$ is unclear Prove by induction of $n$
$$\sum_{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


*

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



*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.

 [/INST] 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$.
</s>