5
$\begingroup$

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?

  • 0
    @user6312: ty!!2011-04-05

3 Answers 3

0

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

  • 0
    @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)\:.$2011-04-05
4

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.