# Homework Help: Induction with sum on left and right side.

1. Mar 18, 2012

### Tremoi

1. The problem statement, all variables and given/known data
Does
$\sum_{k=1}^{n}(\frac{1}{2k-1} - \frac{1}{2k}) = \sum_{k=1}^{n}\frac{1}{k + n}$
hold for $1 \leq n$

2. Relevant equations

3. The attempt at a solution
It holds for n = 1. I assume that it should be done with induction but I can't find a way actually compare the two sums to each other. I then had an idea about maybe putting each sum on a common denominator and prove that the both denominators and the both numerators are equal but that's not true so I don't really know where to start.
The left terms can be rewritten as $\frac{1}{2k(2k-1)}$ as well but that havent really helped me either.

2. Mar 18, 2012

### praharmitra

You can prove this using induction. Using the usual induction techniques, define $f(n) = \sum\limits_{k=1}^{k=n}\left(\frac{1}{2k-1} - \frac{1}{2k}\right)$. You want to show $f(n) = \sum\limits_{k=1}^{k=n} \frac{1}{k+n}$. You've already shown that this is true for $n=1$. Assuming the statement is true for $n$
$$f(n+1)\\ = \sum\limits_{k=1}^{k=n+1}\left(\frac{1}{2k-1} - \frac{1}{2k}\right) = f(n) + \frac{1}{2n+1} - \frac{1}{2n+2} \\ = \sum\limits_{k=1}^{k=n} \frac{1}{k+n}+ \frac{1}{2n+1} - \frac{1}{2n+2}$$
Now changing the variable in the sum $k \to k' = k-1$. The sum becomes
$$f(n+1) \\ = \sum\limits_{k'=0}^{k'=n-1} \frac{1}{k'+n+1}+ \frac{1}{2n+1} - \frac{1}{2n+2} \\ = \sum\limits_{k'=1}^{k'=n-1} \frac{1}{k'+n+1} + \frac{1}{n+1}+ \frac{1}{2n+1} - \frac{1}{2n+2}\\ = \sum\limits_{k'=1}^{k'=n-1} \frac{1}{k'+n+1}+ \frac{1}{2n+1} + \frac{1}{2n+2}\\ =\sum\limits_{k'=1}^{k'=n+1} \frac{1}{k'+n+1}$$

Thus, the statement is true!

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook