0
$\begingroup$

Using Mathematical Induction I need to prove that

$ \sum_{i = 1}^n \frac{1}{\sum_{n = 0}^i n} = \frac{2n}{n+1}$

As A first step I verified it for numbers 1 and 2 which worked

Secondly I simplified the LHS as:

$ \frac{1}{\sum n} = \frac{1}{\frac {n(n+1)}{2}} = \frac{2}{n(n+1)}$

which converts my problem into

$ \frac{2}{1 \cdot 2} + \frac{2}{2 \cdot 3} + \frac{2}{3 \cdot 4} ......... + \frac{2}{n \cdot (n+1)} = \frac{2n}{n+1} $

After which I cancel out 2 as the common factor from both sides. But at this stage I am stuck and am unable to go forward. What should I do next ?

$\endgroup$
3
$\begingroup$

This is known as a Telescoping Series. To solve these, you use the method of Partial Fractions, in which you solve the equation $\frac A{n+1}+\frac B n=\frac1{n(n+1)}$, where $A$ and $B$ are constants. This will allow you to split up the function into something like the form $(\frac1 1-\frac 1 2)+(\frac 1 2 -\frac 1 3)+(\frac 1 3-\frac 1 4)+...$, which you can regroup into $\frac1 1-(\frac 1 2+\frac 1 2 )-(\frac 1 3+\frac 1 3)-(\frac 1 4+...=1-0-0-...$. Notice that the end term will not cancel out.

If you just want an induction proof, just substitute $n+1$ for $n$ and look for the value you got for $n$ on both sides, subtract that from both sides, and prove that what remains on both sides is equal.

$\endgroup$
1
$\begingroup$

Straightforward. After simplifying your expression, proceed with your induction. $$\sum_{i=1}^{n+1} \dfrac{2}{i(i+1)} = \sum_{i=1}^{n} \dfrac{2}{i(i+1)} + \frac{2}{(n+1)(n+2)} = \frac{2n}{n+1} + \frac{2}{(n+1)(n+2)} = \frac{2n^2+4n+2}{(n+1)(n+2)} = \frac{2(n+1)}{n+2} $$

$\endgroup$
  • $\begingroup$ +1 because this answer actually gives a proof for induction. My answer just glosses over it in the end. $\endgroup$ – AlgorithmsX Nov 20 '16 at 4:08
1
$\begingroup$

To do this by induction, I start at the OP's simplification

$\sum_{k=1}^n \frac1{k(k+1)} =\frac{n}{n+1} $.

This is true for $n=1$, where it says $\frac12 = \frac12$.

If it is true for $n$, then

$\begin{array}\\ \sum_{k=1}^{n+1} \frac1{k(k+1)} &=\sum_{k=1}^{n} \frac1{k(k+1)}+\frac1{(n+1)(n+2)}\\ &=\frac{n}{n+1}+\frac1{(n+1)(n+2)}\\ &=\frac{n(n+2)+1}{(n+1)(n+2)}\\ &=\frac{n^2+2n+1}{(n+1)(n+2)}\\ &=\frac{(n+1)^2}{(n+1)(n+2)}\\ &=\frac{n+1}{n+2}\\ \end{array} $

and it is true for $n+1$.

Therefore it is true for all $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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