# Thread: Axiom of Induction Uh Oh

1. ## 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

2. Hello UC151CPR
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 $P(n)$ (a statement about $n$ that may or may not be true) as follows:

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

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

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

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

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

$\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)}$

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

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

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

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

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

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

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

This one is fine
$
\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?
$
=\color{red}\frac{(k+1)^2}{(k+1)(k+2)}
$

4. Originally Posted by Jones

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

This one is fine
$
\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?
$
=\color{red}\frac{(k+1)^2}{(k+1)(k+2)}
$
$\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)}$

5. First, we must assume that the statement is correct for some positive integer n. That is, $\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:

$\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

$\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:

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

$\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)} =$ $\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 $\frac{n+1}{n+2}$. But so is the RHS, so we conclude that (*) holds and therefore the equation is correct.