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

[sre2f]

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.

 

[stunner5000pt]

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.

for the first n integers the formula is n(n+1)/2

first of all don't 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

 

[HallsofIvy]

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!

 

[sre2f]

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...

 

[hypermonkey2]

well ya, it is an inductive proof i suppose. but i wouldn't 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. here's 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

 

[sre2f]

...

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.

...

I am not seeing where you get n(n+1) out of the addition...

 

[amcavoy]

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:

$$\sum_{k=1}^{n}k-\sum_{k=1}^{n}(k-1)=n$$

 

[sre2f]

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:

$$\sum_{k=1}^{n}k-\sum_{k=1}^{n}(k-1)=n$$

I did that method and got 0 points out of 30 for the problem...

 

[Berko]

B/c if you did it that way, you did not use induction.

 

[Galileo]

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

$$\square$$
$$\square \square$$
$$\square \square \square$$
$$\square \square \square \square$$
$$\vdots$$
$$\vdots$$
$$\square \square \square \square \dots \dots \square$$

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.

 

[sre2f]

B/c if you did it that way, you did not use induction.

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.

 

[amcavoy]

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.

Then why didn't you receive credit? Unless I'm missing something, that method shows it works.

 

[hypermonkey2]

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!