Proving the sum of the first $n$ natural numbers by induction I am currently studying proving by induction but I am faced with a problem.
I need to solve by induction the following question.
$$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$    
for all $n > 1$.
Any help on how to solve this would be appreciated.

This is what I have done so far.
Show truth for $N = 1$ 
Left Hand Side = 1
Right Hand Side = $\frac{1}{2} (1) (1+1) = 1$
Suppose truth for $N = k$
$$1 + 2 + 3 + ... + k = \frac{1}{2} k(k+1)$$
Proof that the equation is true for $N = k + 1$
$$1 + 2 + 3 + ... + k + (k + 1)$$
Which is Equal To
$$\frac{1}{2} k (k + 1) + (k + 1)$$
This is where I'm stuck, I don't know what else to do. The answer should be:
$$\frac{1}{2} (k+1) (k+1+1)$$
Which is equal to:
$$\frac{1}{2} (k+1) (k+2)$$
Right?
By the way sorry about the formatting, I'm still new.

Think of pairing up the numbers in the series. The 1st and last (1 + n) the 2nd and the next to last (2 + (n - 1)) and think about what happens in the cases where n is odd and n is even.
If it's even you end up with n/2 pairs whose sum is (n + 1) (or 1/2 * n * (n +1) total)
If it's odd you end up with (n-1)/2 pairs whose sum is (n + 1) and one odd element equal to (n-1)/2 + 1 ( or 1/2 * (n - 1) * (n + 1) + (n - 1)/2 + 1 which comes out the same with a little algebra).
