Results 1 to 13 of 13
Like Tree5Thanks
  • 1 Post By HallsofIvy
  • 1 Post By RLBrown
  • 1 Post By JeffM
  • 1 Post By romsek
  • 1 Post By JeffM

Math Help - Mathematical induction

  1. #1
    Member srirahulan's Avatar
    Joined
    Apr 2012
    From
    Srilanka
    Posts
    173

    Post Mathematical induction

    using the Mathematical induction method to prove this ,

    \Sigma_{r=1}^{n}n(n+2r)=n(2n+1) In this problem can i start with substitute n=1 and continue or substitute r=1 and continue...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34

    Re: Mathematical induction

    substitute n=1 and do summation for r and then it is true for n so prove it for n+1 using n
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,977
    Thanks
    1643

    Re: Mathematical induction

    There is no "r" to substitute 1 for! The "r" is a "dummy"- it takes on values of 1 up to n so it would not make sense to "substitute 1" for it.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,653
    Thanks
    1063

    Re: Mathematical induction

    Quote Originally Posted by srirahulan View Post
    using the Mathematical induction method to prove this ,

    \Sigma_{r=1}^{n}n(n+2r)=n(2n+1) In this problem can i start with substitute n=1 and continue or substitute r=1 and continue...
    as with most induction problems show that $P(1)=True$ and that $P(n) \Rightarrow P(n+1)$

    $P(1) = \left\{\displaystyle{\sum_{r=1}^1}1(1+2r)=1(2\cdot 1 + 1)\right\}=\left\{3=3\right\}=True$

    I leave it to you to show that $P(n) \Rightarrow P(n+1)$ i.e. that

    $\left\{\displaystyle{\sum_{r=1}^n}n(n+2r)=n(2n+1) \right\} \Rightarrow \left\{\displaystyle{\sum_{r=1}^{n+1}}(n+1)((n+1)+ 2r)=(n+1)(2(n+1)+1)\right\} $
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2014
    From
    United States
    Posts
    4
    Thanks
    7

    Re: Mathematical induction

    Quote Originally Posted by srirahulan View Post
    using the Mathematical induction method to prove this ,

    \Sigma_{r=1}^{n}n(n+2r)=n(2n+1) In this problem can i start with substitute n=1 and continue or substitute r=1 and continue...
    \Sigma_{r=1}^{n}n(n+2r)=n^2(2n+1)
    Is easier to prove
    Click Here
    Last edited by RLBrown; April 13th 2014 at 02:39 PM.
    Thanks from HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member srirahulan's Avatar
    Joined
    Apr 2012
    From
    Srilanka
    Posts
    173

    Re: Mathematical induction

    when i show n=p is true then what do i add both side L.H.S and R.H.S to shoe n=p+1 is true?????
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34

    Re: Mathematical induction

    hint:for n=p+1 in summation break it into summation for p and then for 1 term and then use substitution for 2rn term from p(n)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member srirahulan's Avatar
    Joined
    Apr 2012
    From
    Srilanka
    Posts
    173

    Question Re: Mathematical induction

    If n=p then,
    \Sigma_{r=1}^{p}(p+2r)=p(2p+1)
    Then i write like this
    \Sigma_{r=1}^{p}P+2\Sigma_{r=1}^{p}r=p(2p+1)
    Then add 2(p+1) both side then i comes like this,
    \Sigma_{r=1}^{p}p+2\Sigma_{r=1}^{p+1}r=p(2p+1)+2(p  +1)
    But what about this >> \Sigma_{r=1}^{p}p
    please give me a solution????????
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34

    Re: Mathematical induction

    substitute summation of p from r=1 to p with the eqn u get in n=p
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    662
    Thanks
    340

    Re: Mathematical induction

    $\displaystyle \sum_{r = 1}^n\{n(n + 2r)\} = n\left\{\sum_{r = 1}^n(n + 2r)\right\} = n\left\{\left(\sum_{r=1}^nn\right) + 2\left(\sum_{r=1}^nr\right)\right\} = n\left(n^2 + 2 * \dfrac{n(n + 1)}{2}\right) =$

    $n\left(n^2 + 2 * \dfrac{n^2 + n}{2}\right) = n(n^2 + n^2 + n) = n(2n^2 + n) = n^2(2n + 1) \ne n(2n + 1)\ unless\ n = 0\ or\ n = 1.$

    $\displaystyle n = 2 \implies \sum_{r = 1}^2\{2(2 + 2r)\} = 2(2 + 2 * 1) + 2(2 + 2 * 2) = 2 * 4 + 2 * 6 = 8 + 12 = 20 =$

    $4 * 5 = 2^2(2 * 2 + 1)\ne 2(2 * 2 + 1).$

    $\displaystyle n = 3 \implies \sum_{r = 1}^3\{3(3 + 2r)\} = 3(3 + 2 * 1) + 3(3 + 2 * 2) + 3(3 + 2 * 3) = 3(5 + 7 + 9) = 3 * 21 = 3 * 3 * 7 =$

    $3^2(2 * 3 + 1) \ne 3(2 * 3 + 1).$

    The student is trying to prove a falsity and so is understandably having trouble. I suggest we ask the student to check what the actual proposition to be proven is.

    EDIT: Romsek is correct. RL Brown identified that what was trying to be proved is false several posts back. I am leaving my post up, however, because this student needs it spelled out.
    Last edited by JeffM; April 14th 2014 at 08:08 AM. Reason: Acknowledge RL Brown's priority
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,653
    Thanks
    1063

    Re: Mathematical induction

    I believe RLBrown identified it in post #5
    Thanks from JeffM
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    662
    Thanks
    340

    Re: Mathematical induction

    I think this student is struggling enough to warrant an answer.

    The intuition behind proofs by induction is this: if something is true for the next integer if it is true for this integer and if that something is also true for 1, then it is true for 2, which means it is true for 3, which means it is true for 4, and so on forever and ever and ever. Got the intuition?

    Now for the proof that a proposition P(n) is true for every positive integer n, the structure of a proof by weak mathematical induction is this:

    Step 1: Prove P(1) is true.

    Now this means that there is at least one positive integer for which P is true. Choose an arbitrary one of such positive integers (call it k). So P(k) is true. This is frequently called the "induction hypothesis." It is not a mere assumption. You have proved in step 1 that such numbers exist.

    Step 2: Prove P(k + 1) is true given that P(1) and P(k) are true and k is a positive integer.

    Let's do this for your problem.

    $\displaystyle Prove\ by\ induction\ that\ n\ is\ any\ positive\ integer \implies \left\{\sum_{r = 1}^nn(n + 2r)\right\} = n^2(2n + 1).$

    Now as a practical matter I like to see whether the proposition is true for 2 and 3 before I do the proof so I don't waste time on trying to prove a falsity, but that is NOT part of a formal proof. OK Formal proof

    Step 1

    $\displaystyle n = 1 \implies \left\{\sum_{r = 1}^nn(n + 2r)\right\} = 1(1 + 2 * 1) = 1(2 * 1 + 1) = 1^2(2 * 1 + 1) = n^2(2n + 1).$

    Thus there exists a positive integer k such that $\displaystyle \left\{\sum_{r = 1}^kk(k + 2r)\right\} = k^2(2k + 1) = 2k^3 + k^2.$

    Step 2

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

    $\displaystyle \left\{\sum_{r = 1}^k(k + 1)(\{k + 1\} + 2r)\right\} + 3k^2 + 6k + 3 =$

    $\displaystyle \left\{\sum_{r = 1}^kk\{1 + (k + 2r)\right\} + \left\{\sum_{r = 1}^k1(\{k + 1\} + 2r)\right\} + 3k^2 + 6k + 3 =$

    $\displaystyle \left\{\sum_{r = 1}^kk\right\} + \left\{\sum_{r = 1}^kk(k + 2r)\right\} + \left\{\sum_{r = 1}^k(k + 1 + 2r)\right\} + 3k^2 + 6k + 3 =$

    $\displaystyle k^2 + (2k^3 + k^2) + \left\{\sum_{r = 1}^k(k + 1 + 2r)\right\} + 3k^2 + 6k + 3 =$

    $\displaystyle 2k^3 + 5k^2 + 6k + 3 + \left\{\sum_{r = 1}^k(k + 1 + 2r)\right\}=$

    $\displaystyle 2k^3 + 5k^2 + 6k + 3 + \left\{\sum_{r = 1}^kk\right\} + \left\{\sum_{r = 1}^k1\right\} + \left\{\sum_{r = 1}^k2r\right\}=$

    $\displaystyle 2k^3 + 5k^2 + 6k + 3 + k^2 + k + 2 * \left\{\sum_{r = 1}^kr\right\}=$

    $\displaystyle 2k^3 + 6k^2 + 7k + 3 + 2 * \left\{\sum_{r = 1}^kr\right\}=$

    $2k^3 + 6k^2 + 7k + 3 + 2 * \dfrac{k(k + 1)}{2} =$

    $2k^3 + 6k^2 + 7k + 3 + k^2 + k=$

    $2k^3 + 7k^2 + 8k + 3= (k + 1)(2k^2 + 5k + 3) = (k + 1)(k + 1)(2k + 3) = (k + 1)^2(2k + 2 + 1) =$

    $(k + 1)^2\{(2(k + 1) + 1\}.$ QED
    Thanks from romsek
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,653
    Thanks
    1063

    Re: Mathematical induction

    QED indeed!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction (2)
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 15th 2008, 07:28 AM
  3. Mathematical Induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 4th 2007, 04:33 PM
  4. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: August 3rd 2007, 12:16 AM
  5. mathematical induction again
    Posted in the Algebra Forum
    Replies: 5
    Last Post: July 31st 2007, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum