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.

This is an example from my textbook. I'm very rusty with simplifying algebraic expression so i hope you'll forgive me for that.

The textbook says there are two rules to Mathematical Induction:

1) We must first prove that $P(1)$ is true.

2) We must then assume that $P(k)$ is true and prove that $P(k+1)$ is true.

Show that if n is a positive integer, then $1 + 2+· · ·+n =\frac{ n(n + 1)} 2$

For the inductive hypothesis we assume that P(k) holds for an arbitrary positive integer k. That is, we assume that

$1 + 2+· · ·+k = \frac{k(k + 1)} 2$ .

Under this assumption, it must be shown that P(k + 1) is true, namely, that $1 + 2+· · ·+k + (k + 1) =\frac {(k + 1)((k + 1) + 1)} 2= \frac{(k + 1)(k + 2)} 2$

is also true. When we add $k + 1$ to both sides of the equation in P(k), we obtain

$1 + 2+· · ·+k + (k + 1) =\frac{k(k + 1)} 2 + (k + 1) = \frac{k(k + 1) + 2(k + 1)} 2$

$= \frac{(k + 1)(k + 2)} 2$ .

This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step.

My question is how this proves that $P(k+1)$ is true? Also, why does textbook add $k+1$ to both sides of the equation?

share|improve this question
    
Related: math.stackexchange.com/questions/19485/… –  JavaMan Oct 30 '12 at 18:26
    
After some thinking, I see how the answer makes sense. –  Unknown Oct 30 '12 at 18:28
add comment

2 Answers

up vote 1 down vote accepted

You are corect that what we want to show is that assuming: $$1 + 2 + \cdots + k = \frac{k(k+1)}{2} \hspace{40mm} (1)$$ it is also true that: $$1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}. \hspace{10mm} (2)$$

So to do this we are aloud to manipulate the expression we know to be true. Now since we know $(1)$ we area allowed to manipulate it. The idea is it's easy to transform the left side of $(1)$ into the left side of $(2)$ by adding $k + 1$. This is why the textbook adds $k +1$ to both sides of equation $(1)$.

Now when we do this we get $$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+2)(k+1)}{2}.$$

So now we have shown that, assuming (1) is true (2) must also be true, which is why this proves that P(k+1) is true.

EDIT: To adress the comment, it is from the fact that $\frac{2}{2} = 1$: $$\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + (k+1)\cdot1 = \frac{k(k+1)}{2} + (k+1)\cdot\frac{2}{2}= \frac{k(k+1)}{2} + \frac{2(k+1)}{2}$$

share|improve this answer
    
Could you possibly show me how $\frac{k(k+1)}2 + (k+1)$ becomes $\frac{k(k+1)}2 + \frac{2(k+1)}2$ ? I ask simply because I have a poor math background, so occasionally I come across equation that would seem simple but don't make sense to me. –  Unknown Oct 30 '12 at 18:39
    
@BernieMacinflor Sure no problem, I just put it in the answer via an edit. –  Deven Ware Oct 30 '12 at 18:44
add comment

For some reason, I had trouble with this question.

The answer is $\frac{(k+1)(k+2)}2$

My brain interpreted the answer as some random equation that had no relation to $\frac{n(n+1)}2$

I can now see that $(k+1)=n$ and $(n+1)=(k+2)$

So that makes sense for part 1 of the trouble I was having with this question.

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.