Proof by induction for "sum-of"

Question

Prove that for all $n \ge 1$:

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

What I have done currently:

Proved that theorem holds for the base case where n=1.

Then:

Assume that $P(n)$ is true. Now to prove that $P(n+1)$ is true:

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

So: $$\sum_{k=1}^{n+1} \frac{1}{k(k+1)} = \frac{n+1}{n+2}$$

However, how do I proceed from here?

Answer 1

This step is wrong:

$$\sum_{k=1}^{n+1} 1/k(k+1) = n/(n+1) + n+1$$

it should read:

$$\sum_{k=1}^{n+1} \dfrac{1}{k(k+1)} = \dfrac{n}{n+1} + \dfrac{1}{(n+1)(n+2)}$$

so we have:

$$\sum_{k=1}^{n+1} \dfrac{1}{k(k+1)} = \dfrac{n(n+2)+1}{(n+1)(n+2)}$$

$$= \dfrac{n^2+2n+1}{(n+1)(n+2)}$$

$$= \dfrac{(n+1)^2}{(n+1)(n+2)}$$

$$= \dfrac{n+1}{n+2}$$

Answer 2

$$\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1},$$ hence $$\begin{eqnarray*} \sum_{k=1}^{n}\frac{1}{k(k+1)} &=& \sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{n}\frac{1}{k+1}\\&=&\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=2}^{n+1}\frac{1}{k}\\&=&1-\frac{1}{n+1} = \frac{n}{n+1}.\end{eqnarray*}$$ For short: the LHS is a telescopic sum.

Answer 3

For n=1:

$$ \sum_{k=1}^{1} 1/(k(k+1))=1/2=1/(1+1) $$

Let's prove it for $n+1$:

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

But using our assumption for $P(n)$ : $$ \sum_{k=1}^{n} \frac{1}{k(k+1)}=\frac{n}{n+1} $$

So the sum will be:

$$ \sum_{k=1}^{n+1} \frac{1}{k(k+1)}=\frac{n}{(n+1)} + \frac{1}{(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} $$

Hence proved.

Note that you made a mistake in your last part where you wrote:

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

Answer 4

Since the other answer doesn't use induction, here's an induction proof.

Base case: We use the smallest value for $n$ and check that the form works. The smallest value is $n=1$, in this case, the sum on the LHS is $$ \sum_{k=1}^1\frac{1}{k(k+1)}=\frac{1}{1(1+1)}=\frac{1}{2}. $$ Also, the RHS is $$ \frac{1}{1+1}=\frac{1}{2}. $$ Since the LHS and the RHS are equal, the claim holds when $n=1$.

Inductive case: We assume that the claim is true for $n=m$ and prove the claim is true for $n=m+1$. Therefore, we have assumed that $$ \sum_{k=1}^m\frac{1}{k(k+1)}=\frac{m}{m(m+1)} $$ and we can use this fact as if it were true.

We want to prove that the statement is true when $n=m+1$, in other words, when $$ \sum_{k=1}^{m+1}\frac{1}{k(k+1)}=\frac{m+1}{(m+1)(m+2)}. $$ We can't use this statement because it's the next one (the one we want to prove).

We can, however, use the inductive hypothesis to build up to the next step. Since $$ \sum_{k=1}^m\frac{1}{k(k+1)}=\frac{m}{m(m+1)} $$ we observe that the sum on the LHS is almost the sum that we need for the next case. What's missing from the sum on the LHS is the $m+1$-st term. In other words, we are missing the case where we plug in $m+1$ for $k$ which is $\frac{1}{(m+1)(m+1)}$.

WARNING: The OP added $(m+1)$ to both sides and not the $m+1$-st term.

If we add this term to both sides we get $$ \frac{1}{(m+1)(m+2)}+\sum_{k=1}^m\frac{1}{k(k+1)}=\frac{m}{m(m+1)}+\frac{1}{(m+1)(m+2)}. $$ The LHS is just the sum $$ \sum_{k=1}^{m+1}\frac{1}{k(k+1)}$$ and the RHS simplifies to the fraction $$ \frac{m+1}{(m+1)(m+2)}. $$ This proves the claim when $n=m+1$.

Then, by the PMI, the claim is true for all integers $n\geq 1$.

Answer 5

Just to address your specific problem regarding induction, there is an error in the way you have introduced the $n+1$ term. You need to add the $n+1$th term onto the sum to $n$ terms:

Assume it is true for $S_n$, so that $$S_n=\Sigma_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1}.$$

Now consider $$S_{n+1}=S_n+\frac{1}{(n+1)(n+2)}=\frac{n}{n+1}+\frac{1}{(n+1)(n+2)}$$ $$=\frac{n^2+2n+1}{(n+1)(n+2)}=\frac{\overline{n+1}}{\overline{n+1}+1}$$ then we are done...