2
$\begingroup$

Prove the following equality using mathematical induction: For any integer $n \ge 1$

$$\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$$

I understand for the base base I need to have $n=1$. If I substituted $n$ for 1 and $i$ for 1 I would get

\begin{align} \sum_{i=1}^{1} \frac{1}{1(1+1)} &= \frac{1}{1+1} \\ \sum_{i=1}^{1} \frac{1}{2} &= \frac{1}{2} \end{align}

As for the inductive step, I inputted $n +1$ but it did not work for me because honestly I did not know what to do with the $i$ and what I should do next. How would I go about doing the next step and an explanation for $i$ would be helpful.

$\endgroup$
  • $\begingroup$ For the inductive step, you must write the formula with $n+1$ and take into account that you have assumed that it is true for $n$. I.e., write it for $n+1$ and use the fact that the sum of the first $n$ terms in the left hand side sum up to $n/(n+1)$. $\endgroup$ – Mauro ALLEGRANZA Jan 14 '14 at 17:51
2
$\begingroup$

HINT:

If $\displaystyle\sum_{i=1}^m \frac1{i(i+1)} = \frac m{m+1}$

$\displaystyle\sum_{i=1}^{m+1} \frac1{i(i+1)}=\sum_{i=1}^m \frac1{i(i+1)}+\frac1{(m+1)(m+1+1)}$ $\displaystyle= \frac m{m+1}+\frac1{(m+1)(m+2)}=\frac1{m+1}\left(m+\frac1{m+2}\right)$

$\displaystyle =\frac1{m+1}\cdot\frac{(m+1)^2}{m+2}=\frac{m+1}{m+2}=\frac{(m+1)}{(m+1)+1}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The second sum should be from $i=1$ to $i=m.$ $\endgroup$ – mathlove Jan 14 '14 at 17:53
  • $\begingroup$ @mathlove, sorry I meant to write the current version $\endgroup$ – lab bhattacharjee Jan 14 '14 at 17:54
  • $\begingroup$ OK. never mind. a good one. $\endgroup$ – mathlove Jan 14 '14 at 17:57
2
$\begingroup$

Hint $\: $ First trivially inductively prove the Fundamental Theorem of Difference Calculus

$$\rm\ F(n)\ =\ \sum_{i\:=\:1}^n\ f(i)\ \ \iff\ \ \ F(n\!+\!1) - F(n)\ =\ f(n),\quad\ F(1) =\: f(1)$$

Yours is $\rm\ F(n)-F(n\!-\!1)\ =\ n/(n\!+\!1)-(n\!-\!1)/n = 1/(n(n\!+\!1)).\,$ Note that by employing the Fundamental Theorem we have reduced the proof to the trivial verification of an equation. No ingenuity is required.

Note that the proof of the Fundamental Theorem is much more obvious than that for your special case because the telescopic cancellation is obvious at this level of generality, whereas it is usually obfuscated in most specific instances. For further discussion see my many posts on telescopy.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Lovely solution, but "by induction" generally does not allow the use of heavy machinery. $\endgroup$ – vadim123 Jan 14 '14 at 18:20
  • $\begingroup$ @vadim123 Don't let the name scare you. There is no "heavy machinery". Said fundamental theorem is perhaps the simplest proof by induction there is. So prove it once and for all, and then all additive telescopic inductive proofs are immediate corollaries, completed simply by verifying said difference equation and initial condition (a completely mechanical calculation for simple $\,f(n)\,$ such as polynomials and rational functions). $\endgroup$ – Gone Jan 14 '14 at 18:28
1
$\begingroup$

Proving these kind of statements always goes the same way. In the induction step, you seperate the last summand $$\sum_{i=1}^{n+1} \frac 1{i(i+1)} = \sum_{i=1}^{n} \frac 1{i(i+1)} + \frac{1}{(n+1)(n+2)},$$ then you can apply the induction hypothesis to get $$\sum_{i=1}^{n+1} \frac 1{i(i+1)} = \frac{n}{n+1} + \frac{1}{(n+1)(n+2)}.$$ Put both fractions on a single denominator and obtain $$\sum_{i=1}^{n+1} \frac 1{i(i+1)} = \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}. \square$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Hint:

Write $$\frac{n}{n+1} = \frac{n+1-1}{n+1} = 1-\frac{1}{n+1}$$

And note that the sum on the left side is a telescop sum. Thus you do not even need induction to proof this.


However, for the induction step, you could write

$$\begin{array}{rcl} \sum_{i=1}^{n+1} \frac{1}{i(i+1)} &=& \frac{1}{(n+1)(n+2)}+\sum_{i=1}^{n} \frac{1}{i(i+1)} \\ &=& 1 - \frac{1}{n+1} + \frac{1}{(n+1)(n+2)} \\ &=& 1 - \frac{n+2}{(n+1)(n+2)} + \frac{1}{(n+1)(n+2)} \\ &=& 1 - \frac{n+2-1}{(n+1)(n+2)}\\ &=& 1 - \frac{1}{n+2}\\ \end{array}$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The extra index does make it a little trickier. Be careful as you work through this problem and always remember that $n$ is the index for induction.

So the inductive hypothesis is that

$$ \sum_{i=1}^n \frac{1}{i(i + 1)} = \frac{n}{n+1} $$

and using this, you want to prove $$ \sum_{i=1}^{n+1} \frac{1}{i(i + 1)} = \frac{n+1}{(n+1)+1} = \frac{n+1}{n+2}. $$

To this end, you can write

$$ \sum_{i=1}^{n+1} \frac{1}{i(i + 1)} = \sum_{i=1}^{n} \frac{1}{i(i + 1)} + \frac{1}{(n+1)(n + 1 + 1)} $$ which by your induction hypothesis, is the same as $$ \frac{n}{n+1} + \frac{1}{(n+1)(n + 1 + 1)} $$

can you finish from here?

| cite | improve this answer | |
$\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.