4
$\begingroup$

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

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


  1. 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.
$\endgroup$

3 Answers 3

10
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ? $\endgroup$
    – Brownie
    Mar 3, 2019 at 3:08
  • 1
    $\begingroup$ @Brownie In the third-to-last step, we observe that $n + 1 \leq n + 2$, so $\frac{2}{n + 1} \geq \frac{2}{n + 2}$, so $- \frac{2}{n + 1} \leq - \frac{2}{n + 2}$. For the second-to-last step, we can see that $\frac{1}{n + 2} = \frac{n + 1}{(n + 1)(n + 2)} = (n + 1) \frac{1}{(n + 1)(n + 2)} \geq \frac{1}{(n + 1)(n + 2)}$. $\endgroup$
    – AJY
    Mar 3, 2019 at 3:12
  • 1
    $\begingroup$ So is this a step you saw you could implement to get the final equal to $ \ n + 1 - \frac{1}{n + 2} $ ? Or is there something that would push you towards doing this? $\endgroup$
    – Brownie
    Mar 3, 2019 at 3:18
  • 2
    $\begingroup$ @Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error. $\endgroup$
    – AJY
    Mar 3, 2019 at 3:21
2
$\begingroup$

If $a\leq b $, then $a+c\leq b+c $ for any $c\in \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}.$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $\frac{n+1}{n+2}$ to both sides, that would be the same? $\endgroup$
    – Brownie
    Mar 3, 2019 at 2:37
  • $\begingroup$ Yes, that would be the same. $\endgroup$ Mar 3, 2019 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.