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

Question

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?

Answer 1

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

Answer 2

Hint $ $ For $ \, f(n)=\rm RHS - LHS\ $ show $ \ f(n\!+\!1) - f(n) = 0 = f(1)$ $\overset{\rm induct}\Longrightarrow\ f(n) = f(1) = 0\,.$

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

Note how a simple transformation reduces inductive proof to the triviality that a function on $ \,\mathbb N\,$ is constant iff its first difference vanishes, i.e. $ \ f(n\!+\!1)-f(n)\ =\ 0.\,$ The inductive proof of this boils down to equality transitivity on a telescoping chain of inequalities $\,f(1) = f(2) = \,\cdots\, = f(n).\,$ While it is intuitively "obvious" that a function that never changes $ \,f(n\!+\!1) = f(n)\,$ is constant $ \,f(n) = f(1)\,$ for all $\,n\in\Bbb N\,$ it does require rigorous proof!

Many inductive proofs aimplify when handled similarly - 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.