Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Feb 1 '13 at 22:19

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

    
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
1  
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
show 1 more comment

4 Answers 4

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Just pull out your induction-proof-template:

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

Details are left as exercise ;-)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.