# How does this prove that P(k) of every k is true?

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?

-
–  JavaMan Oct 30 '12 at 18:26
After some thinking, I see how the answer makes sense. –  Unknown Oct 30 '12 at 18:28

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

-
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

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.

-