Results 1 to 7 of 7

Math Help - Mathematics induction concepts

  1. #1
    Member
    Joined
    Sep 2007
    Posts
    222

    Question Mathematics induction concepts

    I need some help with mathematical induction, especially when related to Computer Science.
    For example:
    1+2+3..+n = n(n+1)/2

    I have to proove for all n. Now the base case is n=1 so
    1 = 1(1+1)/2 = 2/2 = 1

    That part I get but now for any n+1 is where i get confused.
    It is solved like this in a tutorial I read:
    n+1 = ((n+1)((n+1)+1))/2 = ((n^2)+2n+1)/2

    And thats the apparent answer but how does that proove it? I dont get it.

    Thanks
    Phil
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,404
    Thanks
    1293
    Quote Originally Posted by taurus View Post
    I need some help with mathematical induction, especially when related to Computer Science.
    For example:
    1+2+3..+n = n(n+1)/2

    I have to proove for all n. Now the base case is n=1 so
    1 = 1(1+1)/2 = 2/2 = 1

    That part I get but now for any n+1 is where i get confused.
    It is solved like this in a tutorial I read:
    n+1 = ((n+1)((n+1)+1))/2 = ((n^2)+2n+1)/2

    And thats the apparent answer but how does that proove it? I dont get it.

    Thanks
    Phil
    You are correct with the base step.

    Now you need to assume that it is true for n = k.

    Therefore, you assume that

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


    Using this assumption, you have to show that it is true for n = k + 1. In other words, you have to show that

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


    So:

    1 + 2 + 3 + \dots + k + (k + 1)

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

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

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

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


    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2007
    Posts
    222

    Question

    Hmmm still confusing me, I dont get how that prooves n+1?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2007
    Posts
    222

    Question

    I was looking at this:
    Mathematical Induction Tutorial
    Scroll down to the bit saying: "But by the induction hypothesis, k^2 >= 2k, therefore...". Am confused at what is going on there? How did they get the "...>= 2k + 2k + 1..."? Would appreciate an explanation.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Scroll down to the bit saying: "But by the induction hypothesis, k^2 >= 2k, therefore...". Am confused at what is going on there? How did they get the "...>= 2k + 2k + 1..."? Would appreciate an explanation.
    They claim in particular that k^2 + 2k + 1 >= 2k + 2k + 1. This follows from the induction hypothesis that says k^2 >= 2k.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by taurus View Post
    I need some help with mathematical induction, especially when related to Computer Science.
    For example:
    1+2+3..+n = n(n+1)/2

    I have to proove for all n. Now the base case is n=1 so
    1 = 1(1+1)/2 = 2/2 = 1

    That part I get but now for any n+1 is where i get confused.
    It is solved like this in a tutorial I read:
    n+1 = ((n+1)((n+1)+1))/2 = ((n^2)+2n+1)/2

    And thats the apparent answer but how does that proove it? I dont get it.

    Thanks
    Phil
    Hi Phil,

    Proof By Induction attempts to establish an inter-term link.

    It tries to set up a trail of gunpowder as follows...

    The formula being valid for some term n causes it to be valid for the next term.

    Because this is attempted for the general term, which is expressed as the formula,
    what we are in fact doing is proving the following.....

    Formula true for T1 causes it to be true for T2 causes it to be true for T3
    causes it to be true for T4 causes it to be true..........causes it to be true in general.

    You light the trail by testing the first term.
    If it's true for the first term, the gunpowder catches fire.

    In this case, we can prove if the formula is valid or not with the 2 steps mentioned.

    P(k)

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

    P(k+1)

    1+2+3+.......(n-1)+n=\frac{(n+1)}{2}(n+2) hopefully!

    Proof

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

    This is certainly true if P(k) is valid, no doubt about that.

    The important step now is to express this in terms of P(k)

    This is how we try to create that inter-term link.

    \frac{n}{2}(n+1)+(n+1)=(n+1)\left(\frac{n}{2}+1\ri  ght)

    =(n+1)\left(\frac{n}{2}+\frac{2}{2}\right)

    and from this we obtain the P(k+1) version.

    This means that the formula being valid for some n
    causes it to be true for the next n up, the next n after that, on and on....

    Hence if it is valid for a beginning value of n, it's valid for all subsequent ones.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by taurus View Post
    I was looking at this:
    Mathematical Induction Tutorial
    Scroll down to the bit saying: "But by the induction hypothesis, k^2 >= 2k, therefore...". Am confused at what is going on there? How did they get the "...>= 2k + 2k + 1..."? Would appreciate an explanation.

    Thanks
    Hi Phil,

    there are other ways to word the situation...

    What's really meant there is

    "If..... k^2\ge\ 2k

    Then... k^2+(2k+1)\ge\ 2k+(2k+1)

    and since.... k\ge\ 1\ \ \Rightarrow\ 2k\ge\ 1

    which means ... (k+1)^2\ge\ 2(k+1)

    if.... k^2\ge\ 2k

    This establishes the inter-term link.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: August 8th 2010, 08:29 PM
  2. Confusing concepts
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 30th 2010, 05:28 PM
  3. Prove my mathematics induction, trigonometry
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2009, 10:21 PM
  4. Mathematics: Discrete-Mathematics (Algorithems)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2008, 06:27 AM
  5. Mathematics Of Degree (the New Mathematics !!!! )
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: August 26th 2006, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum