Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

I am trying to prove the summation formula using induction:

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

So far I have...

Base case:

• Let n=1 and test

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

$\frac{1}{1(1+1)} = 1-\frac{1}{1+1}$

$\frac{1}{2} = \frac{1}{2}$

• True for n=1

Induction Hypothesis:

• Assume the statement is true for the n-th case

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

Inductive Step:

• Prove, using the Inductive Hypothesis as a premise, that

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

To prove $$ 1-\frac{1}{n+2} = \frac{n+1}{n+2} $$ Multiply both sides by $n+2$ to get an equivalent expression. $$ (1-\frac{1}{n+2}) * (n+2) = (\frac{n+1}{n+2}) * (n+2) $$ $$ n+1=n+2−1 $$

Does this all make sense? How can this be improved upon?

Solution 1:

What do you know about induction proof?

You assume that statement is valid for $P(n)$, and show that is then valid for $P(n+1)$. (basically, you prove $P(n) \implies P(n+1)$.

Then, if the statement is valid for $P(0)$, is valid for $P(1)$, then is valid for $P(2)$ and so on.

This way you proved your statement for every $n \in \mathbb N$.

Back to your problem.

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

Your goal is to show that

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

which should not be too difficult given the previous assumption.

Ask if you have any troubles!

EDIT

How do you manipulate that expression? The goal is to make the premises appear! So just do

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

thanks to the inductive step

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

You just have to prove that this equals $\displaystyle 1- \frac{1}{n+2}$ and you are done

EDIT 2

How do you prove that $$\frac{n+1}{n+2} = 1 - \frac{1}{n+2}$$?

You can multiply both sides by $n+2$ to get an equivalent expression.

$$n+1 = n+2 - 1$$ which is true, and so $\displaystyle \frac{n+1}{n+2} = 1 - \frac{1}{n+2}$ is also true

Solution 2:

True for $\color{brown}{n=1}$: $$\color{brown}{\sum_{k=1}^1\frac1{k(k+1)}}=\frac1{1\cdot2}=\color{brown}{1-\frac1{1+1}}.$$ If true for $\color{blue}{n-1}$, then true for $\color{green}n$: $$\color{green}{\sum_{k=1}^n\frac1{k(k+1)}}=\color{blue}{\sum_{k=1}^{n-1}\frac1{k(k+1)}}+\frac1{n(n+1)}=\color{blue}{1-\frac1n}+\frac1{n(n+1)}=\color{green}{1-\frac1{n+1}}.$$

Solution 3:

Why are you trying to prove it by induction when you can do it in a much more elegant way? Use the fact that $\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$ and the result follows directly, as all other terms except $1$ and $\frac{1}{n+1}$ cancels out.