# Proof by induction: $\sum\limits_{i=1}^{n} \frac{1}{n+i} = \sum\limits_{i=1}^{n} \left(\frac{1}{2i-1} - \frac{1}{2i}\right)$

How can the following be proved by induction? $$\sum\limits_{i=1}^{n} \frac{1}{n+i} = \sum\limits_{i=1}^{n} \left(\frac{1}{2i-1} - \frac{1}{2i}\right)$$ I am out of ideas after practicing for a while: $$\frac{1}{n+1}+\frac{1}{n+2}+\dots+\frac{1}{2n}=\left(1-\frac{1}{2}\right)+\left(\frac{1}{3}-\frac{1}{4}\right)+\dots+\left(\frac{1}{2n-1}-\frac{1}{2n}\right)$$ Does this involve telescoping series?

• Hey, just a hint: This does not involve telescoping series. It's a standard induction, so you just have to think about how the equations change if you insert n+1 instead of n – MichalisN Apr 4 '11 at 23:42
• Why don't you prove this directly? $(1-1/2)=1+1/2-2/2$; also, $(1/3-1/4)=1/3+1/4-2/4$, etc. So, adding the RHS gives you $(1+1/2+\dots+1/2n)-(1+1/2+\dots+1/n)$. – Andrés E. Caicedo Apr 4 '11 at 23:46
• @DJC: I have done the base case, and then tried to show that adding $\frac{1}{2n+1}-\frac{1}{2n+2}$ to both sides does not change the equation. The problem is listed under inductions, so I am thinking it is supposed to be a practice of induction skill, which is what I am doing right now... – inductionist Apr 4 '11 at 23:47
• @inductionist: To get to the "next" sum you add $\frac{1}{2n+1}+\frac{1}{2n+2}$ and subtract $\frac{1}{n+1}$. Which means that you add .... – André Nicolas Apr 4 '11 at 23:54
• @inductionist: OK, more detail. Let $F(n)$ be the left-hand side. What is $F(n+1)$? The first term is now $\frac{1}{n+2}$, the last one is $\frac{1}{2n+2}$. Thus $F(n+1)=F(n)+\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}$. The bit that was "added" to $F(n)$ simplifies to $\frac{1}{2n+1}-\frac{1}{2n+2}$, which is what you need. – André Nicolas Apr 5 '11 at 0:38

$n=1$, check. note that $$\frac{1}{2(n+1)-1}-\frac{1}{2(n+1)}=\frac{(2n+2)-(2n+1)}{(2n+1)(2n+2)}=\frac{1}{(2n+1)(2n+2)}$$ (this is what changes on the rhs for $n+1$). on the left hand side the change is $$\frac{1}{2n+1}+\frac{1}{2n+2}-\frac{1}{n+1}=\frac{(2n+2)+(2n+1)-2(2n+1)}{(2n+1)(2n+2)}=\frac{1}{(2n+1)(2n+2)}$$ as desired.

• thanks, how exactly do you get the left side change? That's the part that gets me stumped, RHS works out pretty well. – inductionist Apr 5 '11 at 0:38
• @inductionist You don't need to perform any magic or pull anything out of a hat - see my answer. There the induction reduces to the trivial induction that a function that does not change, i.e. $\rm\:f(n+1)\ =\ f(n)\:,\$ is constant, $\rm\ f(n)\ =\ f(1)\:.$ – Bill Dubuque Apr 5 '11 at 1:03

HINT $\rm\:$ For $\rm\: f(n)\: =\: RHS - LHS\$ show $\rm\ f(n+1) - f(n) = 0 = f(1)\:,\:$ so induction $\rm\Rightarrow\ f(n) = f(1) = 0\:.$

NOTE $\rm\ \ f(n+1)\ =\ f(n)\$ boils down to $\rm\displaystyle\ \frac{2}{2\:n+2}\ =\ \frac{1}{n+1}\$ by a very simple algebraic calculation.

Notice how a simple transformation has reduced the inductive proof to the triviality that a function on $\rm\:\mathbb N\:$ is constant iff its first difference vanishes, i.e. $\rm\ f(n+1)-f(n)\ =\ 0\:.\:$ The inductive proof of this is a trivial telescoping chain of inequalities $\rm\ f(1)\ =\ f(2)\ =\ \cdots\ =\ f(n)\:.\:$ Note: while it's "obvious" that a function that never changes $\rm\:f(n+1)\ =\ f(n)\:$ is constant $\rm\:f(n)\ =\ f(1)\:,\:$ it does require proof!

Many inductive proofs are best handled in this manner, by transforming the problem so that the induction becomes completely trivial, e.g. that a product of terms $> 1$ is $> 1$. Often, as above, the reduced problem succumbs to a trivial telescopic proof. You can find $\:$ many examples of telescopy in my prior posts here. These methods often serve to reduce inductions to problems that have purely mechanical solution - solvable by using rote algebra with no ingenuity required (e.g. by algorithms in computer algebra systems). For example, the above problem reduces to verifying that a rational function is zero, which requires only simple mechanical polynomial arithmetic.

Proof without using induction:

\begin{align} \text{LHS}&=\sum_{i=1}^n\frac1{n+i}\\ &=\sum_{i=n+1}^{2n}\frac1i\\ &=\sum_{i=1}^{2n}\frac1i-\sum_{i=1}^{n}\frac1i\\ &=\left(\sum_{i=1}^{2n}\frac1i-\frac12\sum_{i=1}^{n}\frac1i\right)-\frac12\sum_{i=1}^{n}\frac1i\\ &=\sum_{i=1}^n\frac1{2i-1}-\sum_{i=1}^n\frac{1}{2i}=\text{RHS}\\ \end{align}

I hope you find it helpful.