# Axiom of Induction Uh Oh

• Oct 15th 2009, 05:58 PM
UC151CPR
Axiom of Induction Uh Oh
Hello MHF.

Let's look at this sequence...
1/[1*2] + 1/[2*3] + 1/[3*4] + ....

Get the pattern?

Yah its...
1/[n(n+1)] = n/[n+1]

So we have...
1/[1*2] + 1/[2*3] + 1/[3*4] + .... + 1/[n(n+1)] = n/[n+1]

I'm supposed to show that the statement holds for all positive integers n.

This will require the use of mathematical induction.

I haven't really learned this yet so be patient. I know I have to show that when n=1 the statement is true.

So we have...

n=1 means that we just do the first term (left side), which is 1/(1*2) = 1/2 or 0.5. The right hand side is 1/(1+1) = 1/2 = 0.5 SAME YAY so far so good!

But then it wants me to show that they n=k and then it wants me to show that n=k+1.

Can someone walk me through these steps?

Thanks
• Oct 15th 2009, 10:46 PM
Hello UC151CPR
Quote:

Originally Posted by UC151CPR
Hello MHF.

Let's look at this sequence...
1/[1*2] + 1/[2*3] + 1/[3*4] + ....

Get the pattern?

Yah its...
1/[n(n+1)] = n/[n+1]

So we have...
1/[1*2] + 1/[2*3] + 1/[3*4] + .... + 1/[n(n+1)] = n/[n+1]

I'm supposed to show that the statement holds for all positive integers n.

This will require the use of mathematical induction.

I haven't really learned this yet so be patient. I know I have to show that when n=1 the statement is true.

So we have...

n=1 means that we just do the first term (left side), which is 1/(1*2) = 1/2 or 0.5. The right hand side is 1/(1+1) = 1/2 = 0.5 SAME YAY so far so good!

But then it wants me to show that they n=k and then it wants me to show that n=k+1.

Can someone walk me through these steps?

Thanks

We set up the statement we want to prove as a propositional function $\displaystyle P(n)$ (a statement about $\displaystyle n$ that may or may not be true) as follows:

$\displaystyle P(n)$ is $\displaystyle \sum_{i=1}^n\frac{1}{i(i+1)}=\frac{n}{n+1}$

We then show that if $\displaystyle P(n)$ is true when $\displaystyle n = k$ (for some integer value of $\displaystyle k$), then it's also true when $\displaystyle n = k+1$ (the next integer). In other words, we show that

$\displaystyle P(k) \Rightarrow P(k+1)$

OK. So let's look at what happens if $\displaystyle P(k)$ is true.

$\displaystyle P(k) \Rightarrow \sum_{i=1}^k\frac{1}{i(i+1)}=\frac{k}{k+1}$

$\displaystyle \Rightarrow \left(\sum_{i=1}^k\frac{1}{i(i+1)}\right)+\frac{1} {(k+1)(k+2)}=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}$

$\displaystyle \Rightarrow \sum_{i=1}^{k+1}\frac{1}{i(i+1)}=\frac{k(k+2)+1}{( k+1)(k+2)}$

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

$\displaystyle =\frac{k+1}{k+2}$

$\displaystyle \Rightarrow\sum_{i=1}^{k+1}\frac{1}{i(i+1)}=\frac{ k+1}{(k+1)+1}$

$\displaystyle \Rightarrow P(k+1)$, since we now have the proposition $\displaystyle P(n)$ where $\displaystyle n$ has the value $\displaystyle (k+1)$

This, together with the fact that you have already proved that $\displaystyle P(1)$ is true, completes the proof.

• Oct 16th 2009, 12:31 AM
Jones

Yes my algebra is beyond bad, but could you explain what you did here ?:

This one is fine
$\displaystyle \Rightarrow \sum_{i=1}^{k+1}\frac{1}{i(i+1)}=\frac{k(k+2)+1}{( k+1)(k+2)}$

How did you get this?
$\displaystyle =\color{red}\frac{(k+1)^2}{(k+1)(k+2)}$
• Oct 16th 2009, 01:04 AM
Defunkt
Quote:

Originally Posted by Jones

Yes my algebra is beyond bad, but could you explain what you did here ?:

This one is fine
$\displaystyle \Rightarrow \sum_{i=1}^{k+1}\frac{1}{i(i+1)}=\frac{k(k+2)+1}{( k+1)(k+2)}$

How did you get this?
$\displaystyle =\color{red}\frac{(k+1)^2}{(k+1)(k+2)}$

$\displaystyle \frac{k(k+2)+1}{(k+1)(k+2)} = \frac{k^2+2k+1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)}$
• Oct 16th 2009, 03:03 AM
Defunkt
First, we must assume that the statement is correct for some positive integer n. That is, $\displaystyle \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3} + ... + \frac{1}{n(n+1)} = \frac{n}{n+1}$ is assumed to be correct.

According to the principle of induction, it will be correct for all positive integers if we prove that, given the assumption that it is correct for some positive integer n, it is also correct for n+1. That is to say, we now need to prove that the following equation:

$\displaystyle \frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + ... + \frac{1}{n(n+1)} + \frac{1}{(n+1)(n+1+1)} = \frac{n+1}{n+1+1}$ (*)

Holds.

However, from the assumption we have, we know that

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

So we can substitute this expression from the LHS of (*), and then we get:

$\displaystyle \frac{n}{n+1} + \frac{1}{(n+1)(n+2)}$ as the LHS.
The RHS of (*) stays $\displaystyle \frac{n+1}{n+2}$. Now we need to prove both sides are equal. Let's play with the left hand side:

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

So the LHS of (*) is equal to $\displaystyle \frac{n+1}{n+2}$. But so is the RHS, so we conclude that (*) holds and therefore the equation is correct.