1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that summation of n(n+1)/2 is true for all integers.

  1. Sep 13, 2005 #1
    Prove that summation of n(n+1)/2 is true for all integers. Why is my proof not valid?

    Could someone explain to me how this is not a valid proof of the summation of "i" from i=1 to n:

    n(n+1)/2

    Show for base cases:

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

    inductive hypothesis: 1+2+...+(n-1)=n(n-1)/2



    ((n-1)*n)/2 + n =
    ((n-1)*n)/2 + 2*n/2 =
    ((n-1)*n + 2*n)/2 =
    ((n-1 + 2)*n)/2 =
    ((n+1)*n)/2 =
    (n*(n+1))/2.
     
    Last edited: Sep 13, 2005
  2. jcsd
  3. Sep 13, 2005 #2
    for the first n integers the formula is n(n+1)/2

    first of all dont use the same variable as given in the quesiton.. use some other positive integer k
    so your inductive hypothesis should look like 1+2+...+k= k(k+1)/2

    for the k+1 part
    you have to prove the summation of the first k+1 integers 1+2+...+(k+1)
    is equal to the formula you have when you sub in k+1 instead which looks like (k+1)(k+2)/2
    and prove the two above statements are the same
     
    Last edited: Sep 13, 2005
  4. Sep 13, 2005 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, I can't tell you because it looks fine to me!

    Of course, it's a bit peculiar. Instead of showing "if the statement is true for n then it is true for n+1", you've shown "if the statement is true for n-1 then it is true for n" but that's exactly the same thing.

    A few stylistic points: while it is a good idea to calculate the formula for several cases to see how to proceed, in the actual proof by induction, it's not necessary to show it for more than n= 1, then show the induction step.
    Also I, personally, prefer not to use the same symbol ("n") in the induction step as for is used in the theorem itself. That can be confused with assuming the statement you want to prove. I prefer to say "if it is true for n= k" and then show that it must be true for "n= k+1".

    (Surely, you're not thinking that in going from "n-1" to "n", you are showing the statement is true "for n"? That might well be grounds for criticism! You are not trying to show the statement is true for "n", you are trying to show it is true for "all positive integers" or "any positive integer, n".)

    Hmm, hypermonkey got in ahead of me but said basically the same thing!
     
    Last edited: Sep 13, 2005
  5. Sep 13, 2005 #4
    Is there another way to prove the summation formula other than induction. I have never been taught induction and just guessed that what I was doing was right. A friend of mine told me it looked like I proved it by induction...
     
  6. Sep 13, 2005 #5
    well ya, it is an inductive proof i suppose. but i wouldnt accept it as a proof were i a professor. its just too random to somehow notice that n(n+1)/2 is the sum of the first n positive integers. heres the proof that i find more fun :

    n = 1 + 2 + 3 + 4......(n-1) + (n)
    n = n + (n-1) + (n-2).......+ 2 + 1 here i just rearranged the terms

    2n = n(n+1) here i just added together the first two equations.

    thus

    n= n(n+1)/2

    you can choose whichever one you like, its just here i find its better because you FIND the formula, rather than find one and see if it works. have fun!

    Bobo
     
  7. Sep 13, 2005 #6

    I am not seeing where you get n(n+1) out of the addition...
     
  8. Sep 13, 2005 #7
    Each adds to (n+1), and that happens n times.

    Another method you could use is called "sequence of differences" (I think that's what it's called). Basically you start with this:

    [tex]\sum_{k=1}^{n}k-\sum_{k=1}^{n}(k-1)=n[/tex]
     
  9. Sep 13, 2005 #8

    I did that method and got 0 points out of 30 for the problem...
     
  10. Sep 14, 2005 #9
    B/c if you did it that way, you did not use induction.
     
  11. Sep 14, 2005 #10

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    A graphical proof is by making a triangle-shape out of squares of sides 1.

    [tex]
    \square [/tex]
    [tex]\square \square [/tex]
    [tex]\square \square \square [/tex]
    [tex]\square \square \square \square [/tex]
    [tex]\vdots[/tex]
    [tex]\vdots[/tex]
    [tex]\square \square \square \square \dots \dots \square [/tex]

    Where the last row has n squares. The area of the triangle is simply the sum of all squares: 1+2+3+...+n
    On the other hand, a real right triangle with sides of length n drawn on that squary-triangle with the hypotenuse connecting the upper left and lower right square has area n^2/2, this hypotenuse cuts square at the end of each row in half. To get the total area of the squary-triangle you have to add 1/2 for each row, so we find n^2/2+n/2=n(n+1)/2.

    Induction may not be the most elegant way, but it's powerful and rigorous. Graphical proofs like this one can be considered too suggestive. Also, writng 1+2+3+..+n instead of summation or sigma notation can be considered suggestive (what do you mean by those dots?). Sounds very fastidious, but that's math sometimes.
     
    Last edited: Sep 14, 2005
  12. Sep 14, 2005 #11
    We did not have to use induction. We were to do it by any method that would give the correct answer. As stated before, we have not been taught induction yet.
     
  13. Sep 14, 2005 #12
    Then why didn't you receive credit? Unless I'm missing something, that method shows it works.
     
  14. Sep 14, 2005 #13
    you get (n + 1) out of the addition, because if you look at the corresponding vertical terms, its
    n
    1

    add them to get n+1

    and then
    (n-1)
    2

    add them to get n+1 and it continues this way n times, since there are n terms in the equation by definition.

    have fun!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove that summation of n(n+1)/2 is true for all integers.
Loading...