Proving by induction that $\sum\limits_{i=1}^n\frac{1}{n+i}=\sum\limits_{i=1}^n\left(\frac1{2i-1}-\frac1{2i}\right)$

Question

I have a homework problem to prove the following via induction: $$\sum_{i=1}^n \frac{1}{n+i} = \sum_{i=1}^n \left(\frac{1}{2i-1} - \frac{1}{2i}\right) $$ The base case is true.

So far I've done the following: $$\sum_{i=1}^{k+1} \frac{1}{(k+1)+i}$$ $$a_{k+1} = \frac{1}{(k+1)+(k+1)} = \frac{1}{2k +2} $$ $$s_k + a_{k+1} = \frac{1}{2k +2} + \sum_{i=1}^k (\frac{1}{2k-1} - \frac{1}{2k}) $$ $$s_{k+1} = \sum_{i=1}^{k+1} (\frac{1}{2(k+1)-1} - \frac{1}{2(k+1)}) $$ $$ \frac{1}{2k +2} + \sum_{i=1}^k (\frac{1}{2k-1} - \frac{1}{2k}) = \sum_{i=1}^{k+1} (\frac{1}{2(k+1)-1} - \frac{1}{2(k+1)}) $$ $$ \frac{1}{2k +2} + \sum_{i=1}^k (\frac{1}{2k-1} - \frac{1}{2k}) = \sum_{i=1}^{k+1} (\frac{1}{2k-1} - \frac{1}{2k+2)}) $$

I'm having a hard time figuring out how to proceed from here. Anyone have any hints or tips for search terms? Or corrections to what I've started above?

Answer 1

Write the left hand side as $f(n)$.

Note that $$f(n+1)-f(n)=\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}$$

That's the key step - that $f(n+1)$ adds two terms to the right of the sum, but subtracts one term from the left.

Answer 2

As Thomas Andrews notes, the key part lies in reindexing the sum (so you can apply the inductive hypothesis, IH). More explicitly, the following is the core part of the inductive argument: \begin{align} \sum_{i=1}^{k+1}\frac{1}{k+1+i}&=\sum_{i=2}^{k+2}\frac{1}{k+i}\tag{reindex}\\[1em] &= \sum_{i=1}^k\frac{1}{k+i}+\frac{1}{2k+2}+\frac{1}{2k+1}-\frac{1}{k+1}\tag{rewrite}\\[1em] &= \sum_{i=1}^k\left(\frac{1}{2i-1}-\frac{1}{2i}\right)+\frac{1}{2k+2}+\frac{1}{2k+1}-\frac{1}{k+1}\tag{IH}\\[1em] &= \sum_{i=1}^k\left(\frac{1}{2i-1}-\frac{1}{2i}\right)+\left(\frac{1}{2k+1}-\frac{1}{2k+2}\right)\tag{simplify}\\[1em] &= \sum_{i=1}^{k+1}\left(\frac{1}{2i-1}-\frac{1}{2i}\right).\tag{rewrite} \end{align}