Showing $1+2+\cdots+n=\frac{n(n+1)}{2}$ by induction (stuck on inductive step)

This is from this website:

Use mathematical induction to prove that $$1 + 2 + 3 +\cdots+ n = \frac{n (n + 1)}{2}$$ for all positive integers $n$.

Solution to Problem 1: Let the statement $P(n)$ be $$1 + 2 + 3 + \cdots + n = \frac{n (n + 1)}{2}.$$

STEP 1: We first show that $P(1)$ is true.

Left Side $= 1$

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

Both sides of the statement are equal hence $P(1)$ is true.

STEP 2: We now assume that $P(k)$ is true
$$1 + 2 + 3 + \cdots + k = \frac{k (k + 1)}{2}$$ and show that $P(k + 1)$ is true by adding $k + 1$ to both sides of the above statement $$ \begin{align} 1 + 2 + 3 + \cdots + k + (k + 1) &= \frac{k (k + 1)}{2} + (k + 1) \\ &= (k + 1)\left(\frac{k}{2} + 1\right) \\ &= \frac{(k + 1)(k + 2)}{2} \end{align} $$ The last statement may be written as $$1 + 2 + 3 + \cdots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$$ Which is the statement $P(k + 1)$.

My question is how in the very last line is the statement $P(k + 1)$ equal to $\frac{(k + 1)(k + 2)}{2}$. I don't get the last step.

Solution 1:

Since this is your first time, I'll try to explain it with an emphasis on clarity. If something isn't clear, just comment and I'll try to explain what's happening.

Claim: You are trying to prove the statement $P(n)$ where $$ P(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$ Your goal is to try to prove this using induction. Proofs by induction usually involve two things: (1) showing that $P(n)$ is true for some fixed value of $n$; this value is oftentimes $n=1$, as it is in your case since you are trying to prove $P(n)$ for all $n\geq 1$. Make sense so far? (2) After you have shown (1) to be true, you then need to assume $P(k)$ to be true for some fixed $k\geq 1$ and then show that $P(k)$ implies $P(k+1)$; that is, you need to show that "if $P(k)$ is true, then $P(k+1)$ is true."

• (1) is called the base case.
• (2) is called the inductive step.

I'll outline the proof below. Let me know if a step doesn't make sense.

Proof. Let $P(n)$ denote the statement $$ P(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$ Base case ($n=1$): Try to see what happens for $P(1)$. We get that $1 = \frac{1(1+1)}{2}$, and this is true. Thus, the base case holds for $n=1$. Inductive step ($P(k)\to P(k+1)$): Assume $P(k)$ is true for some fixed $k\geq 1$ (this is called the inductive hypothesis). That is, assume $$ P(k) : \color{red}{1+2+3+\cdots+k} = \color{green}{\frac{k(k+1)}{2}}\tag{inductive hypothesis} $$ is true. We must show that $P(k+1)$ follows where $$ P(k+1) : \underbrace{\color{red}{1+2+3+\cdots+k}+\color{blue}{(k+1)}}_{\text{LHS or "left-hand side"}} = \underbrace{\color{purple}{\frac{(k+1)((k+1)+1)}{2}}}_{\text{RHS or "right-hand side"}}. $$

Side note: Make sure you understand what just happened with $P(k+1)$. For $P(k)$, we just had $1+2+3+\cdots+k$ on the left-hand side. How come we have $1+2+3+\cdots+k+(k+1)$ now for the left-hand side of $P(k+1)$? This is because we are adding another term to the sum, namely $k+1$ (I highlighted this term with blue). On the right-hand side, where $P(k)$ just had $k$ in its expression, we just replace all of those $k$'s with $k+1$ because we are considering $P(k+1)$. Make sense?

Okay. Starting with the left-hand side of $P(k+1)$, we need to show that the right-hand side of $P(k+1)$ follows. Here's how it works: \begin{align} \text{LHS} &= \color{red}{1+2+3+\cdots+k}+\color{blue}{(k+1)}\tag{by definition}\\[1em] &= \color{green}{\frac{k(k+1)}{2}}+\color{blue}{(k+1)}\tag{by inductive hypothesis}\\[1em] &= \frac{\color{green}{k(k+1)}+\color{green}{2}\color{blue}{(k+1)}}{\color{green}{2}}\tag{common denominator}\\[1em] &= \frac{(k+1)\color{green}{(k+2)}}{\color{green}{2}}\tag{group like terms}\\[1em] &= \color{purple}{\frac{(k+1)((k+1)+1)}{2}}\tag{rearrange}\\[1em] &= \text{RHS} \end{align} Thus, we have shown that the right-hand side of $P(k+1)$ follows from the left-hand side of $P(k+1)$. This completes the inductive step.

Thus, by mathematical induction, the statement $P(n)$ is true for all $n\geq 1$. $\blacksquare$

Does it all make sense now?

Solution 2:

We know that

$P(k) = 1 + 2 + 3 + ... + k$

Therefore:

$P(k+1) = 1 + 2 + 3 + ... + k + (k+1)$

By induction hypothesis we have:

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

so

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

so

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

By induction we now know that since this is true for one integer $k$, it is true for all integers greater than or equal to $k$.

Solution 3:

induction is basically saying that if it is true for this step, it is true for the next step. so assuming $1+2+3...+k=k(k+1)/2$, ie it is true for step k, we have to show that it must be true for step k+1, the next step. the final line shows how, by going through some algebra, adding all the numbers up to k+1 equals putting k+1 into the formula $n(n+1)/2$, written as $1+2+3...+k+[k+1]=[k+1]([k+1]+1)/2$. therefore, if it is true for step 1, it is for step 2, and 3...