Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
1  
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

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.