# Inductions problem?

• Nov 1st 2010, 06:34 AM
Laban
Inductions problem?
I haven't touched induction in a while now, and even after reviewing a bit I still can't figure out how to even start solving this problem :

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...-\frac{1}{2n}=\frac{1}{n+1}+\frac{1}{n+2}+...+\frac {1}{2n}$

now even when I start off putting (n=1) :

I end up with -1/2=1/2 (or maybe I should discard the minus on the left side?)

bottom line - I need help :)

thanks.
• Nov 1st 2010, 08:43 AM
Quote:

Originally Posted by Laban
I haven't touched induction in a while now, and even after reviewing a bit I still can't figure out how to even start solving this problem :

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...-\frac{1}{2n}=\frac{1}{n+1}+\frac{1}{n+2}+...+\frac {1}{2n}$

now even when I start off putting (n=1) :

I end up with -1/2=1/2 (or maybe I should discard the minus on the left side?)

bottom line - I need help :)

thanks.

Notice that your LHS expression goes to..... $-\frac{1}{2n}$

so if $n=1,$ the last term is $-\frac{1}{2(1)}=-\frac{1}{2}$

Hence the LHS for $n=1$ is $1-\frac{1}{2}$
• Nov 1st 2010, 09:40 AM
Laban
I've looked at several examples and all had a series on the LHS and and some kind of single expression on the RHS. so now that I have a series on both sides I don't know how to work with it?

if I had a single expression on the RHS I would simply do :
n=1
then
n=k → n=k+1
and there won't be any problem, but I don't know how to approach having series on both sides?

from what you've told me I assume that for n=1 : $1-\frac{1}{2}=\frac{1}{2}$ right?

thanks.
• Nov 1st 2010, 10:52 AM
emakarov
To use induction, follow these steps.

1. Formulate the statement to prove as: "For all natural numbers n >= n0, P(n)". Here n0 is typically 0 or 1 and P(n) is an expression containing n. It is very important to get P(n) right. In particular, for each particular n, P(n) must be a proposition, i.e., it must be either true or false. One common mistake is to make P(n) a number, like 1 + ... + n. This is a mistake because a number cannot be true or false.

2. Next, you need to know how to substitute various expressions for n in P(n). In particular, the base case is P(n0). For this, replace n everywhere in P(n) with n0. It may sound like this is a problem for kindergarten and I am making fun of you, but so many mistakes can be avoided if people write P(n) and substitute things for n correctly.

3. As has been said, prove P(n0). This is the base case.

4. Prove the following statement: "For all k, P(k) implies P(k + 1)". For this, fix an arbitrary k and assume P(k). I recommend writing, "Induction hypothesis" or "IH" followed by P(k). This is something you can use. Then write what you need to prove: "Need: P(k + 1)". Proceed by proving P(k + 1) and mark the place where you use the induction hypothesis.
• Nov 1st 2010, 11:23 AM
In this case, you can proceed as follows...

P(k)

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+.....-\frac{1}{2k}=\frac{1}{k+1}+\frac{1}{k+2}+\frac{1}{ k+3}+...+\frac{1}{2k}$

P(k+1)

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

We try to show that if P(k) is valid, it will cause P(k+1) to be valid also.

Proof

Starting with P(k), add $\frac{1}{2k+1}-\frac{1}{2k+2}$ to both sides.

If P(k) is valid, then

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+.....-\frac{1}{2k}+\frac{1}{2k+1}-\frac{1}{2k+2}=\frac{1}{k+1}+\frac{1}{k+2}+\frac{1 }{k+3}+...+\frac{1}{2k}+\frac{1}{2k+1}-\frac{1}{2k+2}$

$=\frac{1}{k+2}+\frac{1}{k+3}+....\frac{1}{2k}+\fra c{1}{2k+1}+\left(\frac{1}{k+1}-\frac{1}{2k+2}\right)$

Now you need to show that the brackets contains $\frac{1}{2k+2}$
• Nov 2nd 2010, 04:20 AM
Laban
sorry to bother you like that, I got the solution but missed several parts in your way :

1. for P(k+1) isn't $-\frac{1}{2k}$ missing on the LHS:
$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+.....-\frac{1}{2k}-\frac{1}{2(k+1)}=\frac{1}{k+2}+\frac{1}{k+3}+\frac {1}{k+4}+...+\frac{1}{2(k+1)}$
so that later I could use P(k) LHS to RHS?

2. did you only apply actions to P(k) or did I get it wrong?

3. where did that last part come from - $\frac{1}{k+2}+\frac{1}{k+3}+....\frac{1}{2k}+\frac {1}{2k+1}+\left(\frac{1}{k+1}-\frac{1}{2k+2}\right)$?

anywise, thanks a lot! (Bow)
• Nov 2nd 2010, 04:48 AM
Quote:

Originally Posted by Laban
sorry to bother you like that, I got the solution but missed several parts in your way :

1. for P(k+1) isn't $-\frac{1}{2k}$ missing on the LHS:

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

so that later I could use P(k) LHS to RHS?

2. did you only apply actions to P(k) or did I get it wrong?

3. where did that last part come from - $\frac{1}{k+2}+\frac{1}{k+3}+....\frac{1}{2k}+\frac {1}{2k+1}+\left(\frac{1}{k+1}-\frac{1}{2k+2}\right)$?

anywise, thanks a lot! (Bow)

1. No, I only wrote the last term of the LHS.

The LHS is $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+....-\frac{1}{2k}+\frac{1}{2k+1}-\frac{1}{2k+2}$

To write the P(k+1) proposition, we can just replace k with k+1,
but the series does then go as far as

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

2. We add the two new terms $\frac{1}{2k+1}-\frac{1}{2k+2}$
to both sides of P(k).

The P(k+1) expression has k replaced with k+1 as we are obtaining an expression for the "next n" after n=k.
The idea is that we are trying to prove that "if" the expression is valid for "some n",
then being valid for that n (n=k), it must therefore also be valid for the "next n" (n=k+1).
Valid for n=1 causes the expression to be valid for n=2.
Valid for n=2 causes the expression to be valid for n=3.
Valid for n=3 causes the expression to be valid for n=4.
Valid for n=4 causes the expression to be valid for n=5.
........to infinity.

This is what the P(k), P(k+1) steps are all about.
We are proving whether or not this chain of cause and effect runs through the expression.
Then it's like having a trail of dominoes standing in a line.
When you examine the first domino, you knock them all down
if the expression holds for the first value of n.

3. For the last part, I just moved the first term of the RHS, $\frac{1}{k+1}$ to the end, so that the RHS started at $\frac{1}{k+2}$
• Nov 2nd 2010, 05:23 AM
Laban
so you get this :

$\frac{1}{k+2}+\frac{1}{k+3}+....\frac{1}{2k}+\frac {1}{2k+1}+\frac{1}{2k+2}$

but you still have this expression $\frac{1}{2k}+\frac{1}{2k+1}$ which is not part of what we wrote as P(k+1) but is an obvious part of the series - so do I just leave it as is (cause it's obvious) or do I need to discard of it to make the expression look exactly like how I wrote P(k+1)?

thanks.
• Nov 2nd 2010, 06:15 AM
Quote:

Originally Posted by Laban
so you get this :

$\frac{1}{k+2}+\frac{1}{k+3}+....\frac{1}{2k}+\frac {1}{2k+1}+\frac{1}{2k+2}$

but you still have this expression $\frac{1}{2k}+\frac{1}{2k+1}$ which is not part of what we wrote as P(k+1) but is an obvious part of the series - so do I just leave it as is (cause it's obvious) or do I need to discard of it to make the expression look exactly like how I wrote P(k+1)?

thanks.

Yes, that's ok.

We just used "dots" to indicate that there are lots of "missing terms" that we didn't write.

To make the proposition look clearer...

P(k+1)

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+......-\frac{1}{2(k+1)}=\frac{1}{(k+1)+1}+\frac{1}{(k+1)+ 2}+.......+\frac{1}{2(k+1)}$

We just replace the k with k+1 to get the P(k+1) proposition.
Then we try to get to the P(k+1) proposition from P(k) to discover if there is a cause and effect.

To do that we must add $\frac{1}{2k+1}-\frac{1}{2(k+1)}$ to both sides of P(k).

This is because P(k+1) contains those two extra terms in the LHS
(even though we may only have written one of them... you see this from the pattern of the terms in the series).

Then we want the P(k+1) to start at $\frac{1}{k+2}$ so we shuffle $\frac{1}{k+1}$ to the end and try to obtain the RHS of the original P(k+1) expression we wrote.

This leaves us to add $\frac{1}{k+1}-\frac{1}{2(k+1)}$ and see if we obtain the final term in P(k+1).
• Nov 2nd 2010, 06:23 AM
Laban
thanks a lot! that was really helpful (Yes)(Yes)