Results 1 to 5 of 5

Math Help - Help with induction

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    34

    Help with induction

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, Sabo!

    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.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    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}+\f  rac{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!
    Last edited by Grandad; November 10th 2009 at 07:57 AM. Reason: Add PS
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    34
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum