Results 1 to 7 of 7

Math Help - Mathematical Induction

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    Mathematical Induction

    Hi, I understand the sequence of the example I am working through, but I cannot understand some of the "simplification" (i.e. when one expression is simplified to mean the same thing)

    The example is

    Prove inductively for all integers n >= 1,
    1+2+3....+n =  n(n+1) / 2 ---> *

    i) i understand s(subscript m ??) is true, I prove this by substituting an integer for n

    ii) sn+1 is true when n>=m and sn are true

    To prove for Sk+1 is true for n = k+1;
    original k(k+1)/2 becomes
    k(k+1)/2 + (k+1) ---I understand this is proof for n=k+1 where n is the formula above, marked ---> *

    but I do not understand the next step in the example, where
    (a) k(k+1)/2 + (k+1) <---this formula is simplified to:
    = (b) (k+1)(k+2) / 2 <--- I don't understand how they went from (a) to (b) here.

    I thought
    k(k+1)/2 + (k+1) = k squared + k / 2 + (k+1) (sorry I can't get super/sub script to work)

    Thanks for any help, sorry if my explanation seems jumbled or unreadable(if so I will try to post the example again more clearly)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    <br />
\frac{k(k+1)}{2} + (k+1)<br /> <br /> <br />

    =
    <br />
 \frac{(k+1)(k+2)}{2}<br />


    this is the equation, I don't understand how they got from a to b
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dunsta View Post
    <br />
\frac{k(k+1)}{2} + (k+1)<br /> <br /> <br />

    =
    <br />
 \frac{(k+1)(k+2)}{2}<br />


    this is the equation, I don't understand how they got from a to b
    Don't forget high school algebra brah..

    \frac{k(k+1)}{2}+k+1=\frac{k(k+1)}{2}+\frac{2k+2}{  2}=\frac{k^2+k+2k+2}{2}..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    I didn't think I had forgotten that much algebra, but ...

    <br />
\frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2} ...<br /> <br /> <br />

    oh I get it now, working backwards I see that
    <br />
\frac{(k+1)(k+2)}{2}  = \frac{(k * k) + (k * 2) + (k * 1)+ (1 * 2)}{2}=\frac{k^2 + 2k + k + 2}{2}<br /> <br />

    I just didnt associate (k+1)(k+2) with k^2 + 2k + k + 2
    off the top of my head.

    I will go back over my notes and hope I "get" the problem better next time through.

    Thanks for the help.
    BTW should I have posted this in the algebra formula?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by dunsta View Post

    Thanks for the help.
    BTW should I have posted this in the algebra formula?
    No problem!

    Also, I don't think you would have needed to post this in the algebra forum. Because, despite this really being an algebra problem it is based on the premise of induction which usually goes in this forum.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    One last question on this topic, if I may.

    Is it common knowledge in maths to simplify
    {k^2+3k+2}
    to
    {(k+1)(k+2)}

    as this seems to me to be another way to write the expression rather than a simplification?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by dunsta View Post
    One last question on this topic, if I may.

    Is it common knowledge in maths to simplify
    {k^2+3k+2}
    to
    {(k+1)(k+2)}

    as this seems to me to be another way to write the expression rather than a simplification?
    Hi Dunsta, yes it's just alternative ways to write the same thing.

    It's common in these induction problems because we try to establish an
    infinite chain of cause and effect from the first term all the way through to infinity.

    We try to discover that the formula being valid for n=1 causes it to be valid for n=2...
    then valid for n=2 causes it to be valid for n=3...
    valid for n=3 causes it to be valid for n=4...
    valid for n=4 causes it to be valid for n=5....

    all the way to infinity.

    If we can prove that being valid for n=k causes it to be valid for n=k+1,
    then we have proven all the foregoing in one step!!

    Since this proves that any term k causes the formula to be valid for the next term k+1

    So the induction step establishes whether or not this infinite chain exists.

    In this case

    P(k)

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

    P(k+1)

    substitute k+1 for k

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

    We try to prove that P(k) being true causes P(k+1) to be true

    Hence, we can either multiply out \frac{(k+1)(k+2)}{2}

    and check that it's the same as P(k)+(k+1) multiplied out

    or factor P(k)+(k+1) to see if it equals \frac{(k+1)(k+2)}{2}
    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
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum