Results 1 to 10 of 10

Math Help - Inductions problem?

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    31

    Question 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.
    Last edited by Laban; November 1st 2010 at 05:53 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Laban View Post
    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}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    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}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Laban View Post
    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!
    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}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Laban View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    thanks a lot! that was really helpful
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inequality Inductions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 20th 2009, 10:28 PM
  2. Mathematical Inductions of Combinations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 10th 2009, 07:38 AM
  3. Inductions
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 23rd 2008, 08:57 AM
  4. Mathematical inductions
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 24th 2008, 05:31 PM

Search Tags


/mathhelpforum @mathhelpforum