I'm trying to prove (using induction) that:
$$\sum_{k=1}^n \frac{1}{n+k} = \sum_{k=1}^{2n} \frac{1}{k}(-1)^{k-1}.$$
I have found problems when I tried to establish an induction hypothesis and solving this because I've learned to do things like:
$$ \sum_{k=1}^{n+1} \frac{1}{k}= \sum_{k=1}^{n} \frac{1}{k} + \frac{1}{n+1}.$$
But, in this case, $n$ appears in both parts of summation and I have no idea how make a relation with
$$\sum_{k=1}^n \frac{1}{n+k} $$ and $$\sum_{k=1}^{n+1} \frac{1}{n+1+k}. $$
Because I've seen tha, the case with "$n+1$" should be like:
$$\sum_{k=1}^{n+1} \frac{1}{n+1+k} = \sum_{k=1}^{2n+2} \frac{1}{k}(-1)^{k-1}$$
and I cant find a connection between $$\sum_{k=1}^{n+1} \frac{1}{n+1+k} $$ and $$\sum_{k=1}^{n} \frac{1}{n+k}.$$
Could anyone help me with this?
This is kind of a cute induction proof. The key in this case will be a careful rearrangement of the terms. Let's get started. I'll assume the base case has been checked, so let's move on to the induction step. That is, we assume then that $$ \sum_{k=1}^{2n} (-1)^{k-1}\frac{1}{k} = \sum_{k=1}^n \frac{1}{n+k}. $$ It seems hard (as you've noted!) to look at the right-hand side, so let us focus on manipulating the left-hand side and see where that gets us. If we look at the next terms we would see, we should expect $$ \frac{1}{2n+1} - \frac{1}{2n+2} + \sum_{k=1}^{2n} (-1)^{k-1}\frac{1}{k}. $$ Now, by the induction hypothesis we can replace this last bit with its equivalent form. That is, what we have just written is equal to $$ \frac{1}{2n+1} - \frac{1}{2n+2} + \sum_{k=1}^n \frac{1}{n+k}. $$ So how can this help us? Let us explicitly write this sum out: The whole term we have is $$ \frac{1}{n+1} + \underbrace{\frac{1}{n+2} + \cdots + \frac{1}{2n} + \frac{1}{2n + 1}}_{\text{this is almost the good part!}} - \frac{1}{2n+2} $$ so we just need to find a way to make the two end terms be equal to $+\frac{1}{2n + 2}$. Can you see how that could happen?