# Proving the sum of the first $n$ natural numbers by induction [duplicate]

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.

-

## migrated from stackoverflow.comFeb 1 '13 at 22:19

This question came from our site for professional and enthusiast programmers.

## marked as duplicate by 6005, Mark Bennet, quid, Eric Stucky, BookendJan 8 '15 at 1:23

What do you know about how proofs by induction work? – Brian M. Scott Feb 1 '13 at 22:25
induction is not the simplest proof for this equation. – user59671 Feb 1 '13 at 22:32
You shouldn't be using capital $K$ and lower-case $k$ as if they were interchangeable. Mathematical notation is case-sensitive. – Michael Hardy Feb 1 '13 at 23:54
Your solution is correct, you just have to make the last (very easy!) step: sum up the pieces! :) – Andrea Orta Feb 1 '13 at 23:55
Michael Hardy, Yes I Know About the Capitals, I keep on pressing the Shift key for like every work in the Sentence. :( So Andrea, am I in the right track till now, I mean is everything Good, with equations and such? – Andrew Feb 2 '13 at 0:05

Basic algebra is what's causing the problems: you reached the point

$$\frac{1}{2}K\color{red}{(K+1)}+\color{red}{(K+1)}\;\;\;\:(**)$$

Now just factor out the red terms:

$$(**)\;\;\;=\color{red}{(K+1)}\left(\frac{1}{2}K+1\right)=\color{red}{(K+1)}\left(\frac{K+2}{2}\right)=\frac{1}{2}(K+1)(K+2)$$

-

Are you familiar with how induction works? We first prove this theorem for $n=1$. This is true because $$1 = \frac{1\cdot 2}{2}$$

Now assume that this is true for all values less than $n$, we try to show that it is true for $n$. We have $$1+2+\cdots+n-1+n = \frac{n\cdot (n-1)}{2}+n\\ =\frac{n\cdot (n-1)+2n}{2} = \frac{n^2+n}{2}= \frac{n(n+1)}{2}$$

So it's true for $n=1$, and if it's true for all values less than some number it's true for that number, which means it's true for all numbers.

-

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

-
This is a nice proof, probably the most elementary one available, but it doesn’t answer the question. – Brian M. Scott Feb 1 '13 at 22:24

• What is the base case ($n = 0$, presumably)? Does the formula work?
• Now the induction step: If the formula is true for $n$, show that it is valid for $n + 1$. In this case (as in many sums) this is just to take the identity for $n$ and add the next term to both sides. The left hand side is already what you want, the right hand side probably needs some massage to put in the right form in terms of $n + 1$.