# Question on proof of $1+2+\dots+n=\frac{n(n+1)}{2}$ by induction.

I saw some video where it needs to prove $1+2+\dots+n=\frac{n(n+1)}{2}$ inductively. So it has to be true if $k=1$ and $k+1$ are true.

So, for $k=1$:

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

it is valid.

For $k+1$ here is the proof he does:

\begin{align} 1+2+\dots+k+k+1&=\frac{(k+1)(k+2)}{2} &(1)\\ \frac{k(k+1)}{2}+k+1&=\frac{(k+1)(k+2)}{2} &(2)\\ &=\frac{k^2+2k+k+2}{2}&(3)\\ &=\frac{k^2+3k+2}{2}&(4)\\ &=\frac{(k+1)(k+2)}{2}&\text{factoring (4)} \end{align}

Therefore this formula is valid for $k+1$.

But is this true? I think not. He is just undoing what he have just done. To prove it I think I need to do this:

\begin{align} 1+2+\dots+k+k+1&=\frac{(k+1)(k+2)}{2}\\ \frac{k(k+1)}{2}+k+1&=\frac{(k+1)(k+2)}{2}\\ \frac{k(k+1)+2(k+1)}{2}&=\frac{(k+1)(k+2)}{2}\\ \frac{(k+1)(k+2)}{2}&=\frac{(k+1)(k+2)}{2}\\ (k+1)(k+2)&=(k+1)(k+2)\\ k+1&=k+1\\ k&=k\\ 0&=0\text{ or }1=1 \end{align}

Therefore, $k+1$ is valid in this formula.

Is this right or am I making a mistake somewhere?

• Why $k = k$ implies that $0=0$ or $1=1$? That's is true for every $k$. – Luísa Borsato Jan 27 '17 at 11:45
• It's odd to begin with an equality like this. The correct way would be $1+...+k+k+1 = (1+...+k)+k+1 = (k(k+1)/2) + k+1$ etc. – Max Jan 27 '17 at 11:47

The second way is correct but I would be more carefull and use like this:

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

P.s: Not use the equality in the first place. The problem using the equality is that you need guarantee equivalence in every step what is not so easy in many problems.

Proving for sum =k+1

RhS= $\dfrac {(k)(k+1)}{2} + k + 1$

Which gives

=$\dfrac {(k+1)(k+2)}{2}$

= $\dfrac {([k+1])([k+1] +1)}{2}$

Which means it hold for n and also n+1 !

This proof is at least unlucky written down.

Normally, we start with the claim for $n$ (Here $1+2+\cdots n=\frac{n(n+1)}{2}$) and then proof the claim for $n+1$.

The correct way is to start with $1+2+\cdots n+n+1=\frac{n(n+1)}{2}+n+1$ (we assume that the formula is correct for $n$) and show that this is equal to $\frac{(n+1)(n+2)}{2}$ by simply adding the two fractions.

It is unusual to start with the aim of the induction step and then going back to show that it is valid.

You don't to begin using equality!! You must to arrive in this... $1+2+⋯+k+k+1=$(here you use the induction hipoteses) Than...We start correct:

$$1+2+⋯+k+k+1=**induction hipoteses(ih)**\frac{k(k+1)}{2}**finish(ih)**+**hereyourepeatlikeabove**k+1$$

I hope I've helped.

Sua ultima afirmaçao esta errada. Parece que voce nao entendeu bem a "hipotese de induçao". "Se vale para k+1 entao valera para k".

• People use english here! Not portuguese! – Arnaldo Jan 27 '17 at 11:50
• Why? ok. I can translate for you. – Cappellesso Jan 27 '17 at 11:52
• You don't need translate for me because I speak portuguese, but we have people around the world here and most of them don't understand portuguese. – Arnaldo Jan 27 '17 at 11:55
• I understand, I tried explain it better. Sorry for my English. – Cappellesso Jan 27 '17 at 12:16