# Homework Help: Proof by Induction

1. Oct 18, 2011

### Oriako

1. The problem statement, all variables and given/known data
For each positive integer n, let $$S_{n} = \frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} + ... + \frac{1}{(2n-1)2n}.$$
(a) Calculate $$S_{1}, S_{2}, S_{3}$$. Then use this data to guess a simple formula for $$S_{n}$$.
(b) Prove your guess in part (a) by mathematical induction
(c) Use Result 6.6 on page 136 to give another proof of your guess
(d) Prove that $$\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$$ for all positive real numbers k. Use this to give yet another proof of your guess in part (a). This method of proof is called telescoping.

2. Relevant equations
Result 6.6: For every positive integer n:
$$\frac{1}{(2)(3)} + \frac{1}{(3)(4)} + ... + \frac{1}{(n+1)(n+2)} = \frac{n}{2n+4}.$$

3. The attempt at a solution
Part a)
Since $$S_{1} = \frac{1}{2}, S_{2} = \frac{1}{4}, S_{3} = \frac{1}{6}$$, a good guess would be that $$S_{n} = \frac{1}{2n}$$.

Part b)
For n=1, $$\frac{1}{(2n-1)2n}=\frac{1}{(2(1)-1)2(1)}=\frac{1}{2}$$, so the entire sum is given by $$\frac{1}{n(n+1)} =\frac{1}{(1)((1)+1)} = \frac{1}{2}$$. Thus, $$S_{n} = \frac{1}{2n}$$ is true for n=1. By induction, let k be an arbitrary integer and assume that $$\frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} + ... + \frac{1}{(2k-1)2k} = \frac{1}{2k}$$. We want to prove that $$\frac{1}{(k+1)((k+1)+1)} + \frac{1}{((k+1)+1)((k+1)+2)} + ... + \frac{1}{(2(k+1)-1)(2(k+1))} = \frac{1}{2(k+1)}$$, which when simplified gives: $$\frac{1}{(k+1)(k+2)} + \frac{1}{(k+2)(k+3)} + ... + \frac{1}{(2k+1)(2k+2)} = \frac{1}{2(k+1)}$$.

I don't know where to go from here on (b) and I have no idea how Result 6.6 could help prove the result in a different way, and I'm completely lost on (d) as well. If anyone could help me out that would be massively appreciated, I've been spending hours trying to figure this out. I've run into tons of dead ends and what I've typed up here is the only thing that I know is for sure correct.

Thanks!

2. Oct 18, 2011

### ehild

Assume that the sum is 1/(2k) for n=k, that is

$$S_k=\frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} + ... + \frac{1}{(2k-1)2k} = \frac{1}{2k}$$

Compare it with the sum for n=k+1:

$$S_{k+1}=\frac{1}{(k+1)(k+2)} + \frac{1}{(k+2)(k+3)} + ... +\frac{1}{(2k)(2k+1)} +\frac{1}{(2k+1)(2k+2)} = \frac{1}{2(k+1)}$$
If you subtract 1/(k(k+1)) and add 1/((2k)(2k+1))+1/((2k+1)(2k+2)) to both sides of the sum Sk you get Sk+1.

So $$S_k-\frac{1}{k(k+1)}+\frac{1}{(2k)(2k+1)} +\frac{1}{(2k+1)(2k+2)}=S_{k+1}$$

Substitute Sk=1/(2k) and simplify.

ehild

Last edited: Oct 18, 2011
3. Oct 18, 2011

### Oriako

Thank you for the response!

I already tried what you suggested and got stuck so I thought it was an incorrect way to do it.
From what you suggest, I get

$$\frac{1}{2k} - \frac{1}{k(k+1)} + \frac{1}{(2k+1)(2k+2)} = \frac{(k-1)(2k+1)(2k+2) + (2k^2 + 2k)}{(2k^2 + 2k)(2k+1)(2k+2)}$$ And I am now stuck, I tried typing in the result into Wolframalpha and nothing simpler was given. I'm not sure how this is supposed to simplify to $$\frac{1}{2(k+1)}$$

Also, I haven't made any progress on part (c) or (d) so even a hint if you have some ideas for those ones would be really helpful!

4. Oct 18, 2011

### ehild

Sorry, I left out a term.... I edited my previous post. So the correct formula is

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

The common denominator is 2k(k+1)(2k+1).

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

ehild

5. Oct 18, 2011

### Oriako

Okay, thank you very much. So I think I have a final proof for that part that is correct!

Now, would it be possible for you to help me with part (c)? This is what I've got so far.

Based off of the sum and Result 6.6, I can say that:

$$S_{n} = \sum\limits_{k=n}^{2n-2} \frac{1}{(k+1)(k+2)} = \frac{1}{2n}, T_{n} = \sum\limits_{k=1}^{n} \frac{1}{(k+1)(k+2)} = \frac{n}{2(n+2)}$$
Where, T_{n} is equal to the sum of result 6.6.

A friend told me the following, but I don't understand why any of of it is true.

$$T_{n} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} +... \frac{1}{n}, S_{n} = \frac{1}{n+1} + ... + \frac{1}{n}, T_{2n} = \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{n} + ... + \frac{1}{2n-1} + \frac{1}{2n}, S_{n} = T_{2n} - T_{n} = \frac{1}{2n(2n+1)} - \frac{1}{n(n+1)}$$