Help with induction

Sabo · #1 $Old$ November 10th, 2009, 07:55 AM

I have huge problems with induction exercises, so if I could get a pointer or two on the following exercise (not a full solution preferably) I would appreciate it a lot.

What is the sum of $\sum_{k=1}^n \frac{1}{(2k-1)(2k+1)}$ ? Prove the assumption (assumption the correct term?) by means of induction.

Soroban · #2 $Old$ November 10th, 2009, 08:47 AM

Hello, Sabo!

Quote:

What is the sum of: . $S \;=\;\sum_{k=1}^n \frac{1}{(2k-1)(2k+1)}$ ?

Prove the assumption by means of induction.

First, we must find the formula . . .

We have: . $S \;=\;\sum^n_{k=1}\frac{1}{(2k-1)(2k+1)} \;=\;\frac{1}{1\cdot3} + \frac{1}{3\cdot5} + \frac{1}{5\cdot7} + \hdots$

If you are familiar with "Partial Fractions", this should be familiar.

We will rearrange the function into two fractions:

. . $\frac{1}{(2k-1)(2k+1)} \;=\;\frac{A}{2k-1} + \frac{B}{2k+1}$

Multiply by $(2k-1)(2k+1)\!:\;\;1 \:=\:(2k+1)A + (2k-1)B$

. . Let $k = \text{-}\tfrac{1}{2}\!:\;\;1 \:=\:2A + 0B \quad\Rightarrow\quad A \:=\:\tfrac{1}{2}$

. . Let $k = \tfrac{1}{2}\!:\;\;1 \:=\:0A -2B \quad\Rightarrow\quad B \:=\:\text{-}\tfrac{1}{2}$

Hence: . $S \;=\;\sum^n_{k=1}\left(\frac{\frac{1}{2}}{2k-1} - \frac{\frac{1}{2}}{2k+1}\right) \;=\;\frac{1}{2}\sum^n_{k=1}\left(\frac{1}{2k-1} - \frac{1}{2k+1}\right)$

We have: . $S \;=\;\frac{1}{2}\left[\left(\frac{1}{1} - \frac{1}{3}\right) + \left(\frac{1}{3} - \frac{1}{5}\right) + \left(\frac{1}{5} - \frac{1}{7}\right) + \hdots + \left(\frac{1}{2n-1} - \frac{1}{2n+1}\right)\right]$

Note that most of the fractions cancel out.
. . And we are left with: . $S \;=\;\frac{1}{2}\left(1 - \frac{1}{2n+1}\right) \;=\;\frac{n}{2n+1}$

Therefore: . $\sum^n_{k=1}\frac{1}{(2k-1)(2k+1)} \;=\;\frac{n}{2n+1}$

And that is the assumption that we must prove by Induction.

Grandad · #3 $Old$ November 10th, 2009, 08:55 AM

Hello Sabo

Quote:

Originally Posted by Sabo $View Post$

I have huge problems with induction exercises, so if I could get a pointer or two on the following exercise (not a full solution preferably) I would appreciate it a lot.

What is the sum of $\sum_{k=1}^n \frac{1}{(2k-1)(2k+1)}$ ? Prove the assumption (assumption the correct term?) by means of induction.

Sorry, but I'm not clear exactly what method you are supposed to use to solve this question. As you have posed it (where the sum is not known), this isn't really an induction question. Until we have an Induction Hypothesis, we must use other methods. I will show you another method, and (once we have a solution) the Induction method.

First, then, we can solve this directly by means of Partial Fractions.

Let

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

$\Rightarrow 1 \equiv A(2k+1) +B(2k-1)$

$\Rightarrow A = \tfrac12, B = \tfrac12$

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

Therefore

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

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

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

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

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

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

However, if the question had said:

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

then the method is as follows:

Let $P(n)$ be the proposition $\sum_{k=1}^n \frac{1}{(2k-1)(2k+1)}=\frac{n}{2n+1}$

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

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

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

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

$\Rightarrow P(n+1)$

Now $P(1)$ is $\sum_{k=1}^1 \frac{1}{(2k-1)(2k+1)}=\frac{1}{3}$ , which is true. Therefore by Induction $P(n)$ is true for all $n \ge 1$ .

Grandad

P.S. Ah, I see that Soroban has given you a solution as well. So, you've got lots to look at!

Jameson · #4 $Old$ November 10th, 2009, 09:09 AM

Quote:

Originally Posted by Sabo $View Post$

I have huge problems with induction exercises, so if I could get a pointer or two on the following exercise (not a full solution preferably) I would appreciate it a lot.

What is the sum of $\sum_{k=1}^n \frac{1}{(2k-1)(2k+1)}$ ? Prove the assumption (assumption the correct term?) by means of induction.

Break it into two fractions.

$\frac{A}{2k+1}+\frac{B}{2k-1}=\frac{1}{4k^2-1}$

You should get $\frac{1}{2} \left( \frac{1}{2k-1}-\frac{1}{2k+1} \right)$

Start listing out out some terms and you should see the pattern of cancellation going on.

EDIT: WOW, I'm 3rd in line for this one. At least I got it right

Sabo · #5 $Old$ November 10th, 2009, 09:39 AM

Thanks to all of you. I was quite a bit off in my approach to this problem, but due to the thorough explanations by you guys I am one step closer to understanding induction.

I am a bit upset over the fact that we do not get do to any induction exercises until we hit university here in Sweden. My understanding is that US people get to do it earlier in their education?