2

I'm trying to figure out how to solve this equation by induction and I really don't know where to begin. I have seen some YouTube tutorials, but can't understand how I can go from $k(k+1)$ to $n+1$ in the equation. The task is:

Use induction to show that:

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

Can someone help me solve this equation? Or give me some tips for where to start? I would really appreciate it.

Thanks in advance!

Sirajuddin Asjad
  • 63

3 Answers3

5

To prove this you would first check the base case $n = 1$. This is just a fairly straightforward calculation to do by hand.

Then, you assume the formula works for $n$. This is your "inductive hypothesis". So we have \begin{equation*} \sum_{k = 1}^n \frac 1{k(k + 1)} = \frac n{n + 1}. \end{equation*} Now we can add $\frac 1{(n + 1)(n + 2)}$ to both sides: \begin{align*} \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 + 1)^2}{(n + 1)(n + 2)} \\ &= \frac{(n + 1)}{(n + 1) + 1} \end{align*} But this is exactly the same formula again, just with $n$ replaced by $n + 1$. So if the formula works for $n$, it also works for $n + 1$. And then, by induction, we are done.

Izaak van Dongen
  • 3,791
4

The hint is $$ \sum_{k=1}^{n+1}\frac{1}{k(k+1)} =\biggl(\,\sum_{k=1}^n\frac{1}{k(k+1)}\biggr)+\frac{1}{(n+1)(n+2)} $$ which should equal $$ \frac{n+1}{n+2} $$

egreg
  • 238,574
2

Define the hypothesis $H_n$ as $$H_n : \sum_{k = 1}^n \frac{1}{k(k+1)} = \frac{n}{n+1} $$

For $n = 1$, we have LHS = $\sum \limits_{k = 1}^1 \frac{1}{k(k+1)} = \frac{1}{2} $ and RHS = $\frac{1}{1 + 1} = \frac{1}{2} $ so $H_1$ is true.

Now suppose $H_m$ is true for some integer $m \geq 1$, that is, we have $\sum \limits_{k = 1}^m\frac{1}{k(k+1)} = \frac{m}{m+1}$ as a given.

Then, consider $$\sum_{k = 1}^{m+1} \frac{1}{k(k+1)}$$

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

By induction hypothesis, we have:

$$ = \frac{1}{ (m+1)(m + 2)} + \frac{m}{m+1}$$

$$ = \frac{1 + m(m+2)}{(m+1)(m+2)}$$

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

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

Therefore, $$\sum_{k=1}^{m+1} \frac{1}{k(k+1)} = \frac{m+1}{(m + 1) + 1} $$

So $H_m \implies H_{m+1}$

Since we had $H_1$ true, by induction, $H_n$ is true for all integers $n \geq 1$

rims
  • 2,657