# 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?

-
What have you tried? Where are you stuck? –  JavaMan Apr 4 '11 at 23:27
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 –  Michalis 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)$. –  Andres 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

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

-