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

• Have you used induction before or is this your first time? – Daniel W. Farlow Mar 25 '15 at 22:00
• Do you understand that $p(k+1) = 1 + 2 + 3 + \cdots + k + (k+1)$? – user137731 Mar 25 '15 at 22:05
• crash:This is my first time – Sam Lot Mar 25 '15 at 22:12
• Bye_world:i understand that we are adding k + 1 to both sides in p(k+1)=1+2+3+⋯+k+(k+1) – Sam Lot Mar 25 '15 at 22:13

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?

• What does P in P(n) stand for ? Proof ? – Sam Lot Mar 25 '15 at 23:05
• @SamLot No. $P$ just indicates a statement. I could have used $S(n)$ or $R(n)$ or anything else for that matter. – Daniel W. Farlow Mar 25 '15 at 23:06
• In the inductive step ,what does this "(P(k)→P(k+1))" means ? – Sam Lot Mar 25 '15 at 23:08
• @SamLot It means "$P(k)$ implies $P(k+1)$." The "$\to$" symbol is a mathematical symbol for "implies." – Daniel W. Farlow Mar 25 '15 at 23:09
• It makes more sense now .Thanks – Sam Lot Mar 25 '15 at 23:16

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

• Rather that "we already proved that $1 + 2 + 3 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$" I would say "By induction hypothesis it is $1 + 2 + 3 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$". Note that it was not proved. – mfl Mar 25 '15 at 22:15
• How can we say in the first line that "We know that P(k)=1+2+3+...+k" Where did that come from .Secondly how does the formula in last line P(k+1)=(k+1)(k+2)2 prove that 1+2+3+...+n=n(n+1)2 .How can i link them ? – Sam Lot Mar 25 '15 at 22:27
• In the problem $P(n)$ is defined as $1+2+3+...+n$. $P(k+1) = \frac{(k+1)(k+2)}{2}$ proves that $P(k) = \frac{(k)(k+2)}{2}$ because we have shown that it is true for $1$. Say that $k=1$. We know from these formulas that if the statement is true for a number $k$ it is true for $k+1$. Since it is true for $k+1$, it must be true for $(k+1)+1$ and so on and so on. – OriginalOldMan Mar 25 '15 at 22:33
• When you say "We know that P(k)=1+2+3+...+k Therefore: P(k+1)=1+2+3+...+k+(k+1)" in the last line here you are adding 1 to the left side and k + 1 to the right side .Isnt that mathematically incorrect ? – Sam Lot Mar 25 '15 at 22:40
• We are not adding $1$ to both sides. $P(k)$ is basically the sum of integers from $1$ to $k$. So $P(k+1)$ is the sum of integers from $1$ to $(k+1)$. $k$ is obviously the integer before $(k+1)$. So the sum of integers from $1$ to $(k+1)$ is $1+2+3+...+k+(k+1)$. That's why we can say that $P(k+1) = 1+2+3+...+k+(k+1)$. – OriginalOldMan Mar 25 '15 at 22:44

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

• I dont understand this part from your explanation "adding all the numbers up to k+1 equals putting k+1 into the formula n(n+1)/2".How does those two things 'equal' each other ? – Sam Lot Mar 25 '15 at 22:20
• you show that they equal each other with the algebra: – stanley dodds Mar 26 '15 at 7:00
• $1+2+3...+k=\frac{k(k+1)}2$, the initial statement. add k+1: – stanley dodds Mar 26 '15 at 7:03
• $1+2+3...+k+[k+1]=\frac{k(k+1)}2+k+1$. then rearrange the rhs: – stanley dodds Mar 26 '15 at 7:06
• multiply on rhs: $=\frac{(k+1)(k+2)}2$ which could also be written as $\frac{[k+1]([k+1]+1)}2$. this is the initially presumed equation for k+1, so with. algebra we have shown that if it works for k it works for k+1, and then if it works for that step it works for the next step, and so on – stanley dodds Mar 26 '15 at 7:16