# First principles/induction proof

1. Jul 26, 2008

### forty

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

I need to prove this by first principles and by induction.

I am extraordinarily stuck with this and don't really know where to begin, I've tried writing the LHS in terms of n then trying to simplify but am pretty much stuck. Any suggestions of how to begin for either method would be very much appreciated!

2. Jul 26, 2008

### Defennder

This is an arithmetic progression with d=1. To start off, imagine the sum:
n + n-1 + n-2 + ... + 1 , which is the same as the above, but written in the reverse order. What happens if you add one sum to the other?

3. Jul 26, 2008

### forty

Sorry for my lack of understanding but what do you mean by this..

What happens if you add one sum to the other?

do you mean what happens when you add n + (n-1) + (n-2) and so on? Because if thats what you mean i have no idea >.<

4. Jul 26, 2008

### scast

He means what happens when you sum

1 + 2 + 3 + ... n-2 + n-1 + n
n + n-1 + n-2 + ... + 3 + 2 + 1

5. Jul 26, 2008

### Dick

This is all fine, but the OP needs an inductive proof. Begin by showing the formula is true for say n=1. Let's call P(n)=n(n+1)/2. Now assume 1+...+n=P(n). You want to prove 1+...+(n+1)=P(n+1). Take the difference of the two equations. (n+1)=P(n+1)-P(n). Can you prove that? That's the inductive step.

6. Jul 27, 2008

### HallsofIvy

Staff Emeritus
No, the OP said he needed and proof "from first principles" and an inductive proof. forty and scast were trying to lead him to the first.