3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Uhm, probably you wanted to say "assume that it is true for $n$", and move to the $n+1$ case. $\endgroup$ – Avitus Sep 26 '14 at 8:32
  • 1
    $\begingroup$ This is a telescoping series. $\endgroup$ – Lucian Sep 26 '14 at 9:23
  • 1
    $\begingroup$ @Avitus Thank you. I just worry that I am unclear with my writing! $\endgroup$ – mar10 Sep 26 '14 at 9:55
  • 1
    $\begingroup$ Ah I think I understand what you mean. I will try to correct that to make my notation a bit more professional or formal. $\endgroup$ – mar10 Sep 26 '14 at 10:04
  • 2
    $\begingroup$ Great! The user @Ant has a nice introduction to the notation of proofs by induction. You can take it as inspiration for your amendments. $\endgroup$ – Avitus Sep 26 '14 at 10:07
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well, I understand the statement is valid for Premise(n) and that I must show it will be valid for p(n+1) meaning we prove for every n the statement must be true. The trouble I am having is manipulating one side of the equation (in the inductive step I have created) to show n always with +1 next to it; As in I thought I could manipulate it so whenever you see any n in the equation it will be (n+1), then from there I can simplify to get my answer. I am unsure how to proceed. The concept behind it makes sense, I just think I have trouble getting the algebraic steps in between? $\endgroup$ – mar10 Sep 26 '14 at 8:47
  • $\begingroup$ @mar10 edited. Is it better now? $\endgroup$ – Ant Sep 26 '14 at 8:52
  • $\begingroup$ Ah I think I see what you mean, let me edit my first post! I must sleep shorty, if I cannot figure this out, is there a chance you will be online tomorrow? It is very late where I am. $\endgroup$ – mar10 Sep 26 '14 at 8:54
  • $\begingroup$ @mar10 I probably will. $\endgroup$ – Ant Sep 26 '14 at 8:55
  • 1
    $\begingroup$ @mar10 is it correct. To show that the two numbers are the same just multiply both of them by $n+2$ and simplify $\endgroup$ – Ant Sep 26 '14 at 9:34
2
$\begingroup$

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}}.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your method is much shorter than mine. Is this prefered and complete? I feel as though I need to put more steps in to be more specific and show I really understand it. $\endgroup$ – mar10 Sep 26 '14 at 9:53
  • 1
    $\begingroup$ The principle of our computations is the same: add a term to the sum. This is what really matters, the rest is "routine" work. I think you are putting a little too many intermediate steps. Also note that I used $n-1\to n$ rather than $n\to n+1$, as some terms are shorter. But the appropriate level of details depends on the situation. Isn't it nice with explanatory colors? $\endgroup$ – Yves Daoust Sep 26 '14 at 10:06
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ To better my understanding with induction is why I am using induction in this case! The much more elegant way you suggest is great though. $\endgroup$ – mar10 Sep 26 '14 at 8:49
0
$\begingroup$

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What are you trying to say with this? Sorry for my ignorance. $\endgroup$ – mar10 Sep 26 '14 at 8:48
  • $\begingroup$ @mar10, By inductive hypothesis, $$\sum_{k=1}^m\frac1{k(k+1)}= 1-\frac1{m+1} $$ $\endgroup$ – lab bhattacharjee Sep 26 '14 at 8:51
0
$\begingroup$

Assume for $n-1$ then you will be very clear. I am giving the final step only... $$\sum_{k=1}^{n}\frac{1}{k(k+1)}=\sum_{k=1}^{n-1}\frac{1}{k(k+1)}+\frac 1 {n(n+1)}=1-\frac 1 n+\frac 1 {n(n+1)}=1+\frac {-n-1+1}{n(n+1)}\\=1-\frac {1}{n+1}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This looks like a whole solution! How is this only the final step? $\endgroup$ – mar10 Sep 26 '14 at 9:29

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.