Results 1 to 11 of 11

Math Help - Beginners Number Theory Problem

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Beginners Number Theory Problem

    I just started reading about number theory and here was the first problem verbatim.

    SUM[j=0,n] {j} = n(n+1)/2

    Remarks and Hints: A statement which is proved by induction often has an integral parameter,
    such as n in our case. You then need to do two steps, either of which can be done first:
    (1) You prove that the statement holds for the case n = 1, or whatever the first case is
    that you’re interested in. This is called the base case.
    (2) You prove that IF the statement holds for the case n = k, THEN it holds for the case
    n = k + 1. This is called the inductive step.
    Thus, for step 2, you get to ASSUME the statement for n = k, and show that this is enough
    to imply it for n = k + 1. In your proof, indicate clearly when you’re doing the base case
    and when you’re doing the inductive step.
    So how do I prove this exactly? I know that if I sum j from 0 -> n where n=1 I'll get one, and i know for n=1 that n(n+1)/2 = 1(1+1)/2 = 1 so that makes it true, but what about for the inductive step? What do I do for n=k or n = k+1 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Hi

    The first step consists in verifying that the statement is true for n=1

    \sum_{j=0}^{1} j = 1 = \frac{1.(1+1)}{2}

    For the inductive step you assume that the statement holds for the case n = k

    \sum_{j=0}^{k} j = \frac{k(k+1)}{2}

    And you need to show that \sum_{j=0}^{k+1} j = \frac{(k+1)(k+2)}{2}

    Hint : \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by running-gag View Post
    Hi

    The first step consists in verifying that the statement is true for n=1

    \sum_{j=0}^{1} j = 1 = \frac{1.(1+1)}{2}

    For the inductive step you assume that the statement holds for the case n = k

    \sum_{j=0}^{k} j = \frac{k(k+1)}{2}

    And you need to show that \sum_{j=0}^{k+1} j = \frac{(k+1)(k+2)}{2}

    Hint : \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)
    So do I just substitute in some declared value for k and thats it? Where do I go from here? I lack the actual methodology to solve these types of problems.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    (1) Suppose that you have shown the statement for n=1
    (2) Suppose that you have shown that IF the statement holds for a certain value k THEN it holds for (k+1)

    Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))
    Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))
    etc
    This shows that the statement is true for every n
    This is the methodology

    Now let's prove the inductive step. IF the statement holds for the case n = k
    \sum_{j=0}^{k} j = \frac{k(k+1)}{2}

    Then \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}

    Therefore the statement is true for (k+1)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by running-gag View Post
    (1) Suppose that you have shown the statement for n=1
    (2) Suppose that you have shown that IF the statement holds for a certain value k THEN it holds for (k+1)

    Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))
    Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))
    etc
    This shows that the statement is true for every n
    This is the methodology

    Now let's prove the inductive step. IF the statement holds for the case n = k
    \sum_{j=0}^{k} j = \frac{k(k+1)}{2}

    Then \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}

    Therefore the statement is true for (k+1)
    Here you said the following:

    "Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))
    Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))"
    But in your post before that I saw an example of n=1 and n=k, then n=k+1. I do not see what you are saying for n=2 and n=3 and how you are referencing things to statements(#). (Sorry, I am green to this course, trying to learn)

    Secondly, where did this come from or how did you make this happen:

     \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)

    I'm not up 100% on my summer operator. I'd like to understand how that worked above
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Quote Originally Posted by 1337h4x View Post
    Here you said the following:
    "Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))
    Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))"
    But in your post before that I saw an example of n=1 and n=k, then n=k+1. I do not see what you are saying for n=2 and n=3 and how you are referencing things to statements(#). (Sorry, I am green to this course, trying to learn)
    First you show that the statement is true for n=1.
    Then you show that if it is true for a certain integer k then it is true for (k+1). The first part of this sentence is true for k=1, therefore it is true for 1+1=2 OK?
    Now that it is true for k=2, it is true for 2+1=3
    etc

    Quote Originally Posted by 1337h4x View Post
    Secondly, where did this come from or how did you make this happen:

     \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)

    I'm not up 100% on my summer operator. I'd like to understand how that worked above
     \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k
     \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)

    Therefore  \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)

    Suppose that the statement is true for k
    Then  \sum_{j=0}^{k} j= \frac{k(k+1)}{2}

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

  7. #7
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by running-gag View Post
    First you show that the statement is true for n=1.
    Then you show that if it is true for a certain integer k then it is true for (k+1). The first part of this sentence is true for k=1, therefore it is true for 1+1=2 OK?
    Now that it is true for k=2, it is true for 2+1=3
    etc

     \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k
     \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)

    Therefore  \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)

    Suppose that the statement is true for k
    Then  \sum_{j=0}^{k} j= \frac{k(k+1)}{2}

    Therefore  \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)
    Okay, I guess I need to clarify my questions a little more:

    I understand these statements:

     \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k
     \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)

    But I do not understand this statement:

    Therefore  \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)

    How does this happen? Do you mean this is the same as:

     \sum_{j=0}^{k+1} j = ( \sum_{j=0}^{k} j ) + (k+1)

    And lastly, how did this get formed exactly:

     \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)[/quote]

    I'm curious as to if there is distribution or something with the Sum operator.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Quote Originally Posted by 1337h4x View Post
    Okay, I guess I need to clarify my questions a little more:

    I understand these statements:

     \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k
     \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)

    But I do not understand this statement:

    Therefore  \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)

    How does this happen? Do you mean this is the same as:

     \sum_{j=0}^{k+1} j = ( \sum_{j=0}^{k} j ) + (k+1)
    Yes that's it
    (1)  \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k
    (2)  \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)

    From line (1) to line (2) you add (k+1)
    Therefore  \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)


    Quote Originally Posted by 1337h4x View Post
    And lastly, how did this get formed exactly:

     \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)

    I'm curious as to if there is distribution or something with the Sum operator.
    No
    The hypothesis is that the statement is true for k
     \sum_{j=0}^{k} j = \frac{k(k+1)}{2}

    We have just shown before that  \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)

    You substitute  \sum_{j=0}^{k} j by \frac{k(k+1)}{2}

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

  9. #9
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by running-gag View Post
    Yes that's it
    (1)  \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k
    (2)  \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)

    From line (1) to line (2) you add (k+1)
    Therefore  \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)


    No
    The hypothesis is that the statement is true for k
     \sum_{j=0}^{k} j = \frac{k(k+1)}{2}

    We have just shown before that  \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)

    You substitute  \sum_{j=0}^{k} j by \frac{k(k+1)}{2}

    Therefore  \sum_{j=0}^{k+1} j = \frac{k(k+1)}{2} + (k+1)

    I guess I'm just struggling to understand how we come up with  \frac{k(k+1)}{2} . Could someone explain how we reach this point?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey, USA
    Posts
    36
    OK. Think about this... you want to add the numbers 1 to 100...

    1 + 2 + ... + 100

    Try adding in pairs... one pair at a time...

    1 + 100 = 101

    2 + 99 = 101

    3 + 98 = 101

    4 + 97 = 101

    .

    .

    .

    Does it ring a bell!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Apr 2009
    Posts
    96
    I see a pattern, but I don't see how it answered my question.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another beginners calculus problem
    Posted in the Calculus Forum
    Replies: 4
    Last Post: October 28th 2010, 08:05 AM
  2. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: June 29th 2010, 09:04 AM
  3. Number Theory Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 28th 2009, 03:44 PM
  4. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 30th 2008, 01:07 PM
  5. Replies: 2
    Last Post: December 18th 2008, 06:28 PM

Search Tags


/mathhelpforum @mathhelpforum