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?
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)$
-
0Hey, 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 – 2011-04-04
-
1Why 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)$. – 2011-04-04
-
0@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... – 2011-04-04
-
0@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 .... – 2011-04-04
-
0@user6312: I am not sure how you got there, I think I completely misunderstand the problem... – 2011-04-05
-
1@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. – 2011-04-05
-
0@user6312: ty!! – 2011-04-05
2 Answers
$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.
-
0thanks, how exactly do you get the left side change? That's the part that gets me stumped, RHS works out pretty well. – 2011-04-05
-
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
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.