Results 1 to 2 of 2

Math Help - uncomfortable with induction hypothesis...

  1. #1
    Newbie
    Joined
    Oct 2006
    Posts
    4

    uncomfortable with induction hypothesis...

    Hi guys, I'm totally new to number theory, so bear with me...

    I'm only on page 2 of the textbook and am already stuck

    To prove 1+2+3.... +n = n(n+1)/2, we are supposed to assume 1+2+3...+k = k(k+1)/2 for n<=k, and then add k+1 to both sides, etc. etc.

    Okay, isn't that first assumption the very statement that we are trying to prove, except replacing n with k? Can someone enlighten me as to how this makes sense?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by yc6489 View Post
    Hi guys, I'm totally new to number theory, so bear with me...

    I'm only on page 2 of the textbook and am already stuck

    To prove 1+2+3.... +n = n(n+1)/2, we are supposed to assume 1+2+3...+k = k(k+1)/2 for n<=k, and then add k+1 to both sides, etc. etc.

    Okay, isn't that first assumption the very statement that we are trying to prove, except replacing n with k? Can someone enlighten me as to how this makes sense?
    The general form of an induction proof of a statement S(N) about a natural
    number N is:

    1. Show S(N0) is true for some initial N=N0, this is called the base case
    and N0 is often 0 or 1.

    2. Show that if S(k) is true for some natural number k, then it is also
    true for k+1.

    3. Then as it is true for N0, it is true for N0+1, and then for N0+2, and so
    on, so we conclude that for any natural number N>N0 it is true, as we can
    connect it to the base case by a chain of step 2 above.

    4. As we now have that S(N) is true for any natural N>=N0, we conclude
    that it is true for all naturals >= N0.

    Now your problem is to prove:

    1+2+3.... +n = n(n+1)/2

    for all natural numbers this is our statement S(n). We take as our base case
    n0=1, when S(1) is the assertion:

    1 = 1(2)/2 = 1,

    which is true, so our base case is true.

    Now we assume that S(k) is true for some k and show it true for k+1.
    As we are assuming S(k) is true this is the assumption that:

    1+2+3.... +k = k(k+1)/2.

    Now add (k+1) to each side:

    1+2+3.... +k+(k+1) = k(k+1)/2 + (k+1).

    Rearrange the right hand side of this equation:

    1+2+3.... +k+(k+1) = (1/2)k^2 + (3/2)k +1

    ..........................= (k+1)(k+2)/2

    ..........................= (k+1)[(k+1) + 1]/2.

    But this equation is now S(k+1), which is:

    1+2+3.... +(k+1) = (k+1)[(k+1)+1)/2.

    So from the assumption that S(k) was true we have shown that S(k+1)
    must also be true, combining this with the base case S(1) which we have
    already shown to be true we may conclude by induction that S(n) is true
    for all natural numbers n>=1.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Null Hypothesis, Alternative hypothesis, Critical Region..
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: August 8th 2011, 11:46 PM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Hypothesis on Riemann Hypothesis
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: March 12th 2006, 10:59 AM

Search Tags


/mathhelpforum @mathhelpforum